UOJ Logo Universal Online Judge

UOJ

#239. 【IOI2016】messy

统计

伊尔沙特是一位软件工程师,他的工作是设计高效的数据结构。有一天,他发明了一个新的数据结构,这个数据结构可以存储一个 $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$ 和 $1111$。调用函数 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 = $ 其他限制
120$8$$256$$256$最多有两个下标 $i$ 满足 $p_i \ne i~(0 \le i \le n - 1)$
218$32$$320$$1024$
311$32$$1024$$320$
421$128$$1792$$1792$
530$128$$896$$896$

评测方式

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

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

时间限制:$2\texttt{s}$

空间限制:$2\texttt{GB}$

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

下载

样例及测评库下载