伊尔沙特是一位软件工程师,他的工作是设计高效的数据结构。有一天,他发明了一个新的数据结构,这个数据结构可以存储一个 $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 \le i \le n - 1$。
例如,假设 $n = 4, p = [2, 1, 3, 0]$,你已经插入的整数所对应的二进制表示为 $0000, 1100$ 和 $0111$。调用函数 compile_set
会将元素分别变成 $0000, 0101$ 和 $1110$。
你的任务是写一个程序,该程序通过和数据结构的交互来找到排列 $p$。该程序应该(按照下列顺序):
- 选择一个 $n$ 位整数的集合;
- 将这些整数插入到数据结构中;
- 调用函数
compile_set
来激活 bug; - 检查某些元素是否在修改以后的集合中;
- 利用该信息来判断和返回排列 $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")
returnsfalse
check_element("0010")
returnstrue
check_element("0100")
returnstrue
check_element("1000")
returnsfalse
check_element("0011")
returnsfalse
check_element("0101")
returnsfalse
check_element("1001")
returnsfalse
check_element("0110")
returnsfalse
check_element("1010")
returnstrue
check_element("1100")
returnsfalse
只有一个排列和函数 check_element()
返回的值一致:
排列 $p = [2, 1, 3, 0]$,因此,restore_permutation
应该返回 $[2, 1, 3, 0]$。
子任务
子任务 | 分数 | $n = $ | $w = $ | $r = $ | 其他限制 |
---|---|---|---|---|---|
1 | 20 | $8$ | $256$ | $256$ | 最多有两个下标 $i$ 满足 $p_i \ne i~(0 \le i \le n - 1)$ |
2 | 18 | $32$ | $320$ | $1024$ | 无 |
3 | 11 | $32$ | $1024$ | $320$ | |
4 | 21 | $128$ | $1792$ | $1792$ | |
5 | 30 | $128$ | $896$ | $896$ |
评测方式
评测程序按照以下格式读入输入:
- 第一行:整数 $n, w, r$,
- 第二行:$n$ 个整数,表示排列 $p$ 的元素。
时间限制:$2\texttt{s}$
空间限制:$2\texttt{GB}$