伊尔沙特是一位软件工程师，他的工作是设计高效的数据结构。有一天，他发明了一个新的数据结构，这个数据结构可以存储一个 $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,\dots ,p_{n-1}]$，该序列中 $0$ 到 $n-1$ 这 $n$ 个数字每个数字恰好出现一次，我们称该序列为一个排列。考虑集合终点一个元素，该元素的二进制表达为 $a_0,\dots ,a_{n-1}$（$a_0$ 是最高位）。当函数 compile_set() 被调用时，这个元素将被元素 $a_{p_0},a_{p_1},\dots ,a_{p_{n-1}}$ 替代。

同样的排列 $p$ 会被用于每个元素的二进制位的重排列，这个排列 $p$ 可以是任意一个排列，包括 $p_i=i，0\le i\le 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$ 表示“读”）。

实现细节

你应该实现一个函数（方法）：

• std::vector<int> restore_permutation(int n, int w, int r)
  • $n$：集合中每个元素的二进制表示的位数（也是排列 $p$ 的长度）；
  • $w$：你的程序调用函数 add_element 的最大次数；
  • $r$：你的程序调用函数 check_element 的最大次数；
  • 函数应该返回恢复的排列 $p$。

库函数

为了和数据结构进行交互，你的程序应该使用下列三个函数（方法）

• void add_element(std::string x)，该函数将 $x$ 所描述的元素添加到集合中。
  • $x$：一个由 '0' 和 '1' 构成的字符串，它是要添加到集合中的元素的二进制表示，$x$ 的长度必须是 $n$。
• void compile_set()，该函数必须调用一次且仅能调用一次。在调用该函数后，你的程序不能再调用函数 add_element()。在调用该函数之前，你的程序也不能调用函数 check_element()。
• bool check_element(std::string x)，该函数检查元素 $x$ 是否在修改以后的集合当中。
  • $x$：一个由 '0' 和 '1' 构成的字符串，它是要检查的元素的二进制表示，$x$ 的长度必须是 $n$。
  • 如果元素 $x$ 在修改后的集合中，则返回 true，否则返回 false。

注意：如果你的程序违反上述的任何一条限制，其评分输出将是 “Wrong Answer”。

对于所有的字符串，第一个字符都表示所对应整数的最高位。

评测程序在调用函数 restore_permutation 之前已经确定了排列 $p$。

样例

评测程序执行下列函数调用：

• restore_permutation(4, 16, 16)，我们有 $n=4$ 而且程序最多执行 $16$ 次 “写” 和 $16$ 次 “读” 操作。

程序执行下列函数调用：

• add_element("0001")
• add_element("0011")
• add_element("0100")
• compile_set()
• check_element("0001") returns false
• check_element("0010") returns true
• check_element("0100") returns true
• check_element("1000") returns false
• check_element("0011") returns false
• check_element("0101") returns false
• check_element("1001") returns false
• check_element("0110") returns false
• check_element("1010") returns true
• check_element("1100") returns false

只有一个排列和函数 check_element() 返回的值一致： 排列 $p=[2,1,3,0]$，因此，restore_permutation 应该返回 $[2,1,3,0]$。

子任务

评测方式

评测程序按照以下格式读入输入：

• 第一行：整数 $n,w,r$，
• 第二行：$n$ 个整数，表示排列 $p$ 的元素。

时间限制：$2\mathtt{\text{s}}$

空间限制：$2\mathtt{\text{GB}}$

交互式类型的题目怎么本地测试

下载

样例及测评库下载