AT_joisc2017_e 壊れた機器 (Broken Device)

[problemUrl]: https://atcoder.jp/contests/joisc2017/tasks/joisc2017_e Anna 和 Bruno 是赌术大师。他们将和担任庄家的 D-taro 玩一个游戏。在这个游戏中，Anna 和 Bruno 分别待在不同的房间里。他们只能使用一台损坏的装置相互通信。D-taro 会给 Anna 一个整数。对于 Anna 和 Bruno 来说，这个游戏的目标是使用该装置，把给定的整数从 Anna 传递给 Bruno。 当游戏开始时，一开始，Anna 声明一个整数 $m$，其取值在 1 到 2 000（含）之间。然后他们进行 $Q$ 轮。第 $i$ 轮（$1 \le i \le Q$）按如下方式进行。 1. D-taro 给 Anna 一个整数 $A_i$。 2. Anna 向装置输入数组 $s_i, t_i$。数组 $s_i, t_i$ 的每个元素都必须为 0 或 1。数组 $s_i, t_i$ 的长度必须相同，且长度在 1 到 $m$（含）之间。 3. 令 $u_i$ 为由数组 $s_i$ 和 $t_i$ 通过 **riffle shuffle**（见下文）得到的数组。然后装置将 $u_i$ 发送给 Bruno。 4. Bruno 向 D-taro 发送一个整数。若该整数与 D-taro 给 Anna 的整数 $A_i$ 相同，则 Anna 和 Bruno 在本轮获胜。 请编写实现 Anna 和 Bruno 策略的程序，使他们在全部 $Q$ 轮中都能获胜。 ### 洗牌交错（riffle shuffle） 若能将数组 $Z$ 的元素划分为两组，并满足以下两个条件，则称数组 $Z$ 是由数组 $X$ 和数组 $Y$ 通过 riffle shuffle 得到的。 * 由第一组元素按原有顺序组成的数组等于数组 $X$。 * 由第二组元素按原有顺序组成的数组等于数组 $Y$。 例如，数组 $Z = [1, 1, 1, 0, 0, 0]$ 可由 $X = [1, 1, 0]$ 与 $Y = [1, 0, 0]$ 通过 riffle shuffle 得到，因为由 $Z$ 的第 1、2、4 个元素按原顺序组成的数组为 $[1, 1, 0]$，而由第 3、5、6 个元素按原顺序组成的数组为 $[1, 0, 0]$。 另一方面，若 $X = [1, 1, 0]$、$Y = [1, 0, 0]$，而 $Z = [0, 0, 0, 1, 1, 1]$，则数组 $Z$ 不是由 $X$ 和 $Y$ 通过 riffle shuffle 得到的。 ### 实现细节 你需要提交两个文件。 第一个文件是 `Anna.cpp`。它应实现 Anna 的策略，并实现下列函数。程序应通过预处理指令 `#include` 包含 `Anna.h`。 * `int Declare()` 该函数在开始时被调用一次。 * 返回值是 Anna 声明的整数 $m$。 * 整数 $m$ 必须在 1 到 2 000（含）之间。若不满足此条件，你的程序将被判为 **Wrong Answer [1]**。 * `std::pair Anna(long long A)` 在调用 `Declare` 之后，该函数将被调用 $Q$ 次。第 $i$ 次调用（$1 \le i \le Q$）对应第 $i$ 轮的步骤 1 和步骤 2。 * 参数 $A$ 是 D-taro 给 Anna 的整数 $A_i$。 * 返回值是 Anna 输入到装置中的两个数组 $s_i, t_i$ 组成的二元组。 * 数组 $s_i, t_i$ 的每个元素都必须为 0 或 1。若不满足此条件，你的程序将被判为 **Wrong Answer [2]**。 * 数组 $s_i, t_i$ 的长度都必须在 1 到 $m$（含）之间。若不满足此条件，你的程序将被判为 **Wrong Answer [3]**。 * 数组 $s_i, t_i$ 的长度必须相同。若不满足此条件，你的程序将被判为 **Wrong Answer [4]**。 第二个文件是 `Bruno.cpp`。它应实现 Bruno 的策略，并实现下列函数。程序应通过预处理指令 `#include` 包含 `Bruno.h`。 * `long long Bruno(std::vector u)` 在 Anna 向装置输入数组之后，该函数会被调用一次。总共，该函数会被调用 $Q$ 次。第 $i$ 次调用（$1 \le i \le Q$）对应第 $i$ 轮的步骤 3 和步骤 4。 * 参数 `u` 是装置在第 $i$ 轮发送给 Bruno 的数组 $u_i$。 * 返回值是 Bruno 发送给 D-taro 的整数。 * 返回值必须与 D-taro 给 Anna 的整数 $A_i$ 相同。若不满足此条件，你的程序将被判为 **Wrong Answer [5]**。 ### 重要注意事项 * 你的程序可以实现其他用于内部的函数，或使用全局变量。提交的文件将与评测器一起编译，变成一个可执行文件。所有全局变量和内部函数都应当声明在未命名命名空间中，以避免与其他文件冲突。评测时会以 Anna 进程和 Bruno 进程两个进程形式运行。Anna 进程与 Bruno 进程不能共享全局变量。 * 你的程序不得使用标准输入与标准输出。你的程序不得通过任何方式与其他文件通信。但是，你的程序可以向标准错误输出调试信息。 ### 编译与本地测试 你可以从竞赛网页下载一个压缩包，其中包含用于本地测试你程序的样例评测器。压缩包还包含你程序的样例源代码。 样例评测器为文件 `grader.cpp`。为了测试你的程序，请将 `grader.cpp`、`Anna.cpp`、`Bruno.cpp`、`Anna.h`、`Bruno.h` 放在同一目录下，并运行如下命令以编译程序。 ``` g++ -std=gnu++17 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp ``` 编译成功后，会生成名为 `grader` 的可执行文件。 请注意，实际评测器与样例评测器不同。样例评测器以单进程形式运行，从标准输入读入数据，并将结果写到标准输出。

样例评测器从标准输入读取如下数据。 > $Q$ \ > $A_1$ \ > $A_2$ \ > $\vdots$ \ > $A_Q$

样例评测器向标准输出写出如下信息（引号仅为说明）。 * 若你的程序被判定为正确，它会输出函数 `Declare` 的返回值 $m$，例如 “Accepted: 2000”。 * 若你的程序被判定为任一类 Wrong Answer，样例评测器会写出其类型，例如 “Wrong Answer [1]”。 如果你的程序同时触犯多类 Wrong Answer 的条件，样例评测器只报告其中一种。 样例评测器在每一轮计算 riffle shuffle 时使用伪随机数。其结果在不同执行中不会改变。为了更改伪随机数的种子，请如下方式执行样例评测器。 ``` ./grader 2022 ``` 第一个参数应为一个整数。

#### 约束 * $1 \le Q \le 1\,000$。 * $1 \le A_i \le 1\,000\,000\,000\,000\,000\,000 \ (= 10^{18}) \ (1 \le i \le Q)$。 #### 子任务 1. （5 分）$A_i \le 2\,000 \ (1 \le i \le Q)$。 2. （5 分）$A_i \le 4\,000\,000 \ (1 \le i \le Q)$。 3. （3 分）$A_i \le 10\,000\,000 \ (= 10^7) \ (1 \le i \le Q)$。 4. （12 分）$A_i \le 100\,000\,000 \ (= 10^8) \ (1 \le i \le Q)$。 5. （15 分）$A_i \le 100\,000\,000\,000 \ (= 10^{11}) \ (1 \le i \le Q)$。 6. （60 分）无限制。对于本子任务，你的得分计算如下。 * 令 $m^*$ 为本子任务所有测试中，Anna 声明的整数 $m$ 的最大值。 * 你的得分如下所示。 | $m^*$ 的取值 | 分数 | | :--- | :--- | | $201 \le m^* \le 2\,000$ | $40 - 25 \times \log_{10}\!\left(\dfrac{m^*}{200}\right)$ 分（向下取整为整数） | | $161 \le m^* \le 200$ | 40 分 | | $156 \le m^* \le 160$ | 44 分 | | $151 \le m^* \le 155$ | 48 分 | | $146 \le m^* \le 150$ | 52 分 | | $141 \le m^* \le 145$ | 56 分 | | $m^* \le 140$ | 60 分 | ### 样例通信 下面给出样例评测器的一个样例输入以及相应的函数调用。 #### 样例输入 1 ``` 2 42 2000 ``` | 调用 | 返回值 | | :--- | :--- | | `Declare()` | 4 | | `Anna(42)` | `([0, 0, 1, 0], [1, 1, 0, 1])` | | `Bruno([1, 0, 0, 1, 0, 1, 0, 1])` | 42 | | `Anna(2000)` | `([0, 1], [0, 0])` | | `Bruno([0, 0, 1, 0])` | 2000 | 在该样例输入中，共有 $Q \ (= 2)$ 轮。对于第 1 轮，D-taro 给 Anna 的整数为 $A_1 \ (= 42)$。 对于第 2 轮，D-taro 给 Anna 的整数为 $A_2 \ (= 2000)$。 该样例输入满足所有子任务的约束。