P9512 [JOI Open 2023] 古代机器 2 / Ancient Machine 2

**译自 [JOI Open 2023](https://contests.ioi-jp.org/open-2023/index.html) T1 「[古代の機械 2](https://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2023/ancient2/2023-open-ancient2-statement.pdf) / [Ancient Machine 2](https://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2023/ancient2/2023-open-ancient2-statement-en.pdf)」** **这是一道交互题。** **在提交本题前请务必仔细阅读以下内容。** 本题只支持 C++ 语言提交（建议使用 C++14，请不要使用 C++14 (GCC9)）。 由于洛谷特殊的交互机制，在提交本题时，请去掉代码中的 ```#include "ancient2.h"``` 语句，并将添加以下语句粘贴到代码最开头： ```cpp int Query(int m, std::vector a, std::vector b); ```

Bitaro 和 Bibako 是挖掘和调查 JOI 王国废墟的考古学家。在废墟中，Bitaro 发现了一块古老的石板，Bibako 发现了一台古老的机器。 从研究结果中，Bitaro 发现石板上写有一个长为 $N$ 的字符串 $S$。字符串中每个字符要么是 `0`，要么是 `1`。然而，他还不知道字符串 $S$ 中的每个字符是什么。 另一方面，从研究结果中，Bibako 弄清了如何使用机器。为了使用它，我们需要将石板放在机器上，输入一个整数 $m$ 和两个整数序列 $a,b$，然后做一次查询。这里整数 $m$ 和整数序列 $a,b$ 需满足如下条件： - 整数 $m$ 在 $1$ 和 $1\ 002$ 之间（包括两端）。 - 序列 $a$ 和 $b$ 的长度均为 $m$。 - 序列 $a,b$ 中的元素都是 $0$ 和 $m-1$ 之间的整数（包括两端）。 如果我们把石板放在机器上，输入一个整数 $m$ 和两个整数序列 $a,b$，然后做一次查询，机器会按如下方式操作并显示一个整数。 1. 机器对其**内存区域**置 $0$。 2. 机器进行如下的 $N$ 次操作。第 $i+1$ 次（$0\le i\le N-1$）操作按如下方式进行。 令 $x$ 表示机器内存区域中当前的整数。机器读取字符 $S_i$。这里，$S_i$ 是字符串 $S$ 中的第 $i$ 个字符（下标从 $0$ 开始）。 - 如果 $S_i$ 是 `0`，机器会将内存区域置为 $a_x$。其中 $a_x$ 是序列 $a$ 中第 $x$ 个元素（下标从 $0$ 开始）。 - 如果 $S_i$ 是 `1`，机器会将内存区域置为 $b_x$。其中 $b_x$ 是序列 $b$ 中第 $x$ 个元素（下标从 $0$ 开始）。 3. 这个机器将展示内存区域中最终置为的整数。 使用这个机器，Bitaro 想要确定石板上写的字符串。然而，因为这个机器十分脆弱，查询的次数不能超过 $1\ 000$。此外，输入机器的整数 $m$ 的最大值需要越小越好。 使用这个机器，写一个程序确定石板上写的字符串。 **【实现细节】** 你需要在程序一开始使用预处理指令 `#include` 引入库 `ancient2.h`。它应当实现如下函数。 - `std::string Solve(int N)` 这个函数在每组测试数据中仅被调用一次。这个函数需要返回和石板上所写的字符串 $S$ 相同的字符串。 - 参数 `N` 表示石板上写的字符串 $S$ 的长度 $N$。 - 这个函数需要返回一个长度为 $N$ 的字符串。如果字符串长度不为 $N$，你的程序会被判为 **Wrong Answer [1]**。 - 返回值中每个字符要么是 `0`，要么是 `1`。如果该条件不满足，你的程序会被判为 **Wrong Answer [2]**。 - 返回值应当与石板上写的字符串 $S$ 相同。如果该条件不满足，你的程序会被判为 **Wrong Answer [3]**。 你的程序可以调用如下函数。 - `int Query(int m, std::vector a, std::vector b)` 使用这个函数，你的程序可以做一次查询。 - 参数 `m` 是输入机器的整数 $m$。 - 参数 `a`，`b` 是输入机器的两个整数序列 $a,b$。 - 返回值是当我们把石板放在机器上，并输入上述整数和序列，做一次查询是机器最后显示的整数。 - 参数 `m` 应当在 $1$ 和 $1\ 002$ 之间（包括两端）。如果该条件不满足，你的程序会被判为 **Wrong Answer [4]**。 - 序列 `a` 和 `b` 的长度均应等于 $m$。如果该条件不满足，你的程序会被判为 **Wrong Answer [5]**。 - 序列 `a` 和 `b` 中元素均应在 $0$ 和 $m-1$ 之间（包括两端）。如果该条件不满足，你的程序会被判为 **Wrong Answer [6]**。 - 函数 `Query` 的调用次数不能超过 $1\ 000$ 次。如果超过 $1\ 000$ 次，你的程序会被判为 **Wrong Answer [7]**。 **【注意事项】** - 你的程序可以实现其它函数供内部使用，或者使用全局变量。 - 你的程序禁止使用标准输入输出。你的程序禁止通过任何方式与其他文件通信。然而，你的程序可以将调试信息输出到标准错误输出。 **【编译和测试运行】** 你可以在「文件」中的「附加文件」下载样例 grader 来测试你的程序。「附加文件」中也包含一份你的程序的样例源程序。 样例交互器是文件 `grader.cpp`。为了测试你的程序，你需要将 `grader.cpp`，`ancient2.cpp` 和 `ancient2.h` 三个文件放在同一文件夹下，并且执行如下命令编译你的程序。你也可以运行 `compile.sh` 来编译你的程序。 ```shell g++ -std=gnu++17 -O2 -o grader grader.cpp ancient2.cpp ``` 当编译成功时，会生成一个可执行文件 `grader`。 请注意，实际的交互器和样例不同。样例交互器会作为单进程运行，即它会从标准输入中读取输入数据，并输出结果到标准输出。

第一行一个整数 $N$。 第二行一个长为 $N$ 的字符串 $S$。

样例交互器会输出如下内容到标准输出。 - 如果你的程序被判为正确，它会输出 `Query` 函数中参数 `m` 的最大值，如 `Accepted: 22`。然而，如果你的程序没有调用 `Query` 函数并被判为正确，它会输出 `Accepted: 0`。 - 如果你的程序被判为任一类的答案错误，样例交互器会输出其类别，如 `Wrong Answer [4]`。 如果程序满足多种答案错误的类别，样例交互器只会输出其中一个。

**【样例解释】** 样例函数调用如下。 | 对 `Solve` 的调用 | 返回值 | 对 `Query` 的调用 | 返回值 | | :---------------: | :--------: | :------------------------------------: | :-----------: | | `Solve(3)` | | | | | | | `Query(4, [3, 3, 2, 2], [2, 2, 1, 0])` | `3` | | | | `Query(2, [0, 1], [1, 0])` | `0` | | | | `Query(1, [0], [0])` | `0` | | | | `Query(3, [1, 1, 1], [1, 1, 1])` | `1` | | | `"110"` | | | 假设写在石板上的字符串 $S$ 是 `110`。如果我们把石板放在机器上，输入 $(m,a,b)=(4,[3,3,2,2],[2,2,1,0])$ 并做一次查询，机器将按如下方式操作。 1. 机器将内存区域置为 $0$。 2. 对于第一次操作，因为 $S_0$ 是 `1`，机器会将内存区域置为 $b_0$，即 $2$。 3. 对于第二次操作，因为 $S_1$ 是 `1`，机器会将内存区域置为 $b_2$，即 $1$。 4. 对于第三次操作，因为 $S_2$ 是 `0`，机器会将内存区域置为 $a_1$，即 $3$。 5. 因为最终内存区域被置为的整数是 $3$，所以机器显示 $3$。 注意这组样例输入不满足限制 $N=1\ 000$。在文件中，`sample-02.txt` 满足这个限制。 **【数据范围】** 对于全部数据，满足： - $N=1\ 000$ - $S$ 是一个长为 $N$ 的字符串 - $S$ 中的每个字符要么是 `0`，要么是 `1` 对于每组数据，实际的交互器 **不是**适应性的。这意味着交互器在开始时答案就已经确定了。 如果你的程序在任意一组数据上被判为任意一种答案错误，在本题你将获得 $0$ 分。 如果你的程序在所有数据上都被判为正确，你的分数由 $M$ 确定，其中 $M$ 是所有数据的 `Query` 函数中参数 `m` 的最大值。然而，如果你的程序没有调用 `Query` 函数并且被判为正确，你的分数由 $M=0$ 确定。 - 如果 $103\le M\le 1\ 002$，你的得分为 $10+\lfloor \frac{(1002-M)^2}{9000}\rfloor$ - 如果 $0\le M\le 102$，你将获得 $100$ 分。 这里 $\lfloor x\rfloor$ 表示不超过 $x$ 的最大整数。