P15275 [IOI 2016] Unscrambling a Messy Bug 解读 Bug

**仅支持 C++ 交互。** 你不需要引入额外的头文件，但请在代码头部加入如下内容（也可将其前两行换成其他包含 `std::string` 和 `std::vector` 的头文件）： ```cpp #include #include extern "C" { void add_element(std::string x); bool check_element(std::string x); void compile_set(); std::vector restore_permutation(int n, int w, int r); } ```

伊尔沙特是一位软件工程师，他的工作是设计高效的数据结构。有一天，他发明了一个新的数据结构。这个数据结构可以存储一个 $n$ 位非负整数集合，$n$ 是 $2$ 的整数次幂，即 $n = 2^b$，$b$ 是非负整数。 这个数据结构初始为空。使用该数据结构的程序必须要遵守下列规则： - 程序可以添加一些元素到这个数据结构中，每次利用函数 `add_element(x)` 添加一个元素，每个元素是一个 $n$ 位整数。如果程序要添加的元素已经在数据结构中，则什么事情也不会发生。 - 当添加完最后一个元素以后，程序应该调用一次函数 `compile_set()` ，而且只能调用一次。 - 最后，程序可以调用函数 `check_element(x)` 来检查元素 $x$ 是否在数据结构中。这个函数可以调用多次。 当伊尔沙特第一次实现该数据结构时，他在写函数 `compile_set()` 时出现一个 bug。这个 bug 将集合中每个元素的二进制位以相同的方式重新排序。伊尔沙特希望你能帮助他找到由于该bug导致的重排列。 考虑一个序列 $p = [p_0, \ldots, p_{n-1}]$，该序列中 $0$ 到 $n - 1$ 这n个数字每个数字恰好出现一次。我们称该序列为一个排列。考虑集合中的一个元素，该元素的二进制表达为 $a_0, \ldots, a_{n-1}$（$a_0$ 是最高位）。当函数 `compile_set()` 被调用时，这个元素将被元素 $a_{p_0}, a_{p_1}, \ldots, a_{p_{n-1}}$ 替代。 同样的排列 $p$ 会被用于每个元素的二进制位的重排列。这个排列 $p$ 可以是任意一个排列，包括 $p_i = i$，$0 \leq i \leq n - 1$。 例如，假设 $n = 4$，$p = [2, 1, 3, 0]$，你已经插入的整数所对应的二进制表示为 `0000`，`1100` 和 `0111`。调用函数 `compile_set` 会将三个元素分别变成 `0000`，`0101` 和 `1110`。 你的任务是写一个程序，该程序通过和数据结构的交互来找到排列 $p$。该程序应该（按照下列顺序）： 1. 选择一个 $n$ 位整数的集合， 2. 将这些整数插入到数据结构中， 3. 调用函数 `compile_set` 来激活 bug， 4. 检查某些元素是否在修改以后的集合当中， 5. 利用该信息来判断和返回排列 $p$。 注意你的程序只能调用函数 `compile_set` 一次。 而且，你的程序调用库函数的次数是有限制的。具体的，你的程序可以 - 调用 `add_element` 最多 $w$ 次（$w$ 表示"写"） - 调用 `check_element` 最多调用 $r$ 次（$r$ 表示"读"）。 ### 实现细节 你应该实现一个函数（方法）： - `int[] restore_permutation(int n, int w, int r)` - `n`：集合中每个元素的二进制表示的位数 (也是排列 $p$ 的⻓度）。 - `w`：你的程序调用函数 `add_element` 的最大次数。 - `r`：你的程序调用函数 `check_element` 的最大次数。 - 函数应该返回恢复的排列 $p$。 ### 库函数 为了和数据结构进行交互，你的程序应该使用下列三个函数（方法） - `void add_element(string x)` 该函数将 $x$ 所描述的元素添加到集合中。 - `x`：一个由 `0` 和 `1` 构成的字符串，它是要添加到集合中的元素的二进制表示。x的⻓度必须是 $n$。 - `void compile_set()` 该函数必须调用一次且只能调用一次。在调用该函数之后，你的程序不能再调用函数 `add_element()`。在调用该函数之前，你的程序也不能调用函数 `check_element()`。 - `boolean check_element(string x)` 该函数检查元素 $x$ 是否在修改以后的集合当中。 - `x`：一个由 `0` 和 `1` 构成的字符串，它是要检查的元素的二进制表示。`x` 的⻓度必须是 $n$。 - 如果元素 `x` 在修改后的集合中，则返回 `true`，否则返回 `false`。 注意：如果你的程序违反上述的任何一条限制，其评分输出将是 "Wrong Answer"。 对于所有的字符串，第一个字符都表示所对应整数的最高位。 评测程序在调用函数 `restore_permutation` 之前已经确定了排列 $p$。 请使用提供的模板文件，以获得关于你所使用的编程语言的实现细节。

### 样例评测程序 样例评测程序按照以下格式读入输入： - 第一行: 整数 $n$，$w$，$r$， - 第二行: $n$ 个整数表示排列 $p$ 的元素。 **实际使用的评测程序与样例评测程序略有不同。**

无

### 例子 评测程序执行下列函数调用： `restore_permutation(4, 16, 16)`。我们有 $n = 4$ 而且程序最多执行 $16$ 次"写"和 $16$ 次"读"操作。 程序执行下列函数调用： - `add_element("0001")` - `add_element("0011")` - `add_element("0100")` - `compile_set()` - `check_element("0001")` 返回 `false` - `check_element("0010")` 返回 `true` - `check_element("0100")` 返回 `true` - `check_element("1000")` 返回 `false` - `check_element("0011")` 返回 `false` - `check_element("0101")` 返回 `false` - `check_element("1001")` 返回 `false` - `check_element("0110")` 返回 `false` - `check_element("1010")` 返回 `true` - `check_element("1100")` 返回 `false` 只有一个排列和函数 `check_element()` 返回的值一致： 排列 $p = [2, 1, 3, 0]$。因此，`restore_permutation` 应该返回 `[2, 1, 3, 0]`。 ### 子任务 1. （20 分）$n = 8$，$w = 256$，$r = 256$，最多有两个下标 $i$ 满足 $p_i \neq i$（$0 \leq i \leq n - 1$）， 2. （18 分）$n = 32$，$w = 320$，$r = 1024$， 3. （11 分）$n = 32$，$w = 1024$，$r = 320$， 4. （21 分）$n = 128$，$w = 1792$，$r = 1792$， 5. （30 分）$n = 128$，$w = 896$，$r = 896$。