{"raw_statement":[{"iden":"background","content":"**译自 [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)」**\n\n**这是一道交互题。**\n\n**在提交本题前请务必仔细阅读以下内容。**\n\n本题只支持 C++ 语言提交（建议使用 C++14，请不要使用 C++14 (GCC9)）。\n\n由于洛谷特殊的交互机制，在提交本题时，请去掉代码中的 ```#include \"ancient2.h\"``` 语句，并将添加以下语句粘贴到代码最开头：\n\n```cpp\nint Query(int m, std::vector<int> a, std::vector<int> b);\n```"},{"iden":"statement","content":"Bitaro 和 Bibako 是挖掘和调查 JOI 王国废墟的考古学家。在废墟中，Bitaro 发现了一块古老的石板，Bibako 发现了一台古老的机器。\n\n从研究结果中，Bitaro 发现石板上写有一个长为 $N$ 的字符串 $S$。字符串中每个字符要么是 `0`，要么是 `1`。然而，他还不知道字符串 $S$ 中的每个字符是什么。\n\n另一方面，从研究结果中，Bibako 弄清了如何使用机器。为了使用它，我们需要将石板放在机器上，输入一个整数 $m$ 和两个整数序列 $a,b$，然后做一次查询。这里整数 $m$ 和整数序列 $a,b$ 需满足如下条件：\n\n- 整数 $m$ 在 $1$ 和 $1\\ 002$ 之间（包括两端）。\n- 序列 $a$ 和 $b$ 的长度均为 $m$。\n- 序列 $a,b$ 中的元素都是 $0$ 和 $m-1$ 之间的整数（包括两端）。\n\n如果我们把石板放在机器上，输入一个整数 $m$ 和两个整数序列 $a,b$，然后做一次查询，机器会按如下方式操作并显示一个整数。\n\n1. 机器对其**内存区域**置 $0$。\n\n2. 机器进行如下的 $N$ 次操作。第 $i+1$ 次（$0\\le i\\le N-1$）操作按如下方式进行。\n\n   令 $x$ 表示机器内存区域中当前的整数。机器读取字符 $S_i$。这里，$S_i$ 是字符串 $S$ 中的第 $i$ 个字符（下标从 $0$ 开始）。\n\n   - 如果 $S_i$ 是 `0`，机器会将内存区域置为 $a_x$。其中 $a_x$ 是序列 $a$ 中第 $x$ 个元素（下标从 $0$ 开始）。\n   - 如果 $S_i$ 是 `1`，机器会将内存区域置为 $b_x$。其中 $b_x$ 是序列 $b$ 中第 $x$ 个元素（下标从 $0$ 开始）。\n\n3. 这个机器将展示内存区域中最终置为的整数。\n\n使用这个机器，Bitaro 想要确定石板上写的字符串。然而，因为这个机器十分脆弱，查询的次数不能超过 $1\\ 000$。此外，输入机器的整数 $m$ 的最大值需要越小越好。\n\n使用这个机器，写一个程序确定石板上写的字符串。\n\n**【实现细节】**\n\n你需要在程序一开始使用预处理指令 `#include` 引入库 `ancient2.h`。它应当实现如下函数。\n\n- `std::string Solve(int N)`\n\n  这个函数在每组测试数据中仅被调用一次。这个函数需要返回和石板上所写的字符串 $S$ 相同的字符串。\n\n  - 参数 `N` 表示石板上写的字符串 $S$ 的长度 $N$。\n  - 这个函数需要返回一个长度为 $N$ 的字符串。如果字符串长度不为 $N$，你的程序会被判为 **Wrong Answer [1]**。\n  - 返回值中每个字符要么是 `0`，要么是 `1`。如果该条件不满足，你的程序会被判为 **Wrong Answer [2]**。\n  - 返回值应当与石板上写的字符串 $S$ 相同。如果该条件不满足，你的程序会被判为 **Wrong Answer [3]**。\n\n  你的程序可以调用如下函数。\n\n  - `int Query(int m, std::vector<int> a, std::vector<int> b)`\n\n    使用这个函数，你的程序可以做一次查询。\n\n    - 参数 `m` 是输入机器的整数 $m$。\n    - 参数 `a`，`b` 是输入机器的两个整数序列 $a,b$。\n    - 返回值是当我们把石板放在机器上，并输入上述整数和序列，做一次查询是机器最后显示的整数。\n    - 参数 `m` 应当在 $1$ 和 $1\\ 002$ 之间（包括两端）。如果该条件不满足，你的程序会被判为 **Wrong Answer [4]**。\n    - 序列 `a` 和 `b` 的长度均应等于 $m$。如果该条件不满足，你的程序会被判为 **Wrong Answer [5]**。\n    - 序列 `a` 和 `b` 中元素均应在 $0$ 和 $m-1$ 之间（包括两端）。如果该条件不满足，你的程序会被判为 **Wrong Answer [6]**。\n    - 函数 `Query` 的调用次数不能超过 $1\\ 000$ 次。如果超过 $1\\ 000$ 次，你的程序会被判为 **Wrong Answer [7]**。\n    \n**【注意事项】**\n\n- 你的程序可以实现其它函数供内部使用，或者使用全局变量。\n- 你的程序禁止使用标准输入输出。你的程序禁止通过任何方式与其他文件通信。然而，你的程序可以将调试信息输出到标准错误输出。\n\n**【编译和测试运行】**\n\n你可以在「文件」中的「附加文件」下载样例 grader 来测试你的程序。「附加文件」中也包含一份你的程序的样例源程序。\n\n样例交互器是文件 `grader.cpp`。为了测试你的程序，你需要将 `grader.cpp`，`ancient2.cpp` 和 `ancient2.h` 三个文件放在同一文件夹下，并且执行如下命令编译你的程序。你也可以运行 `compile.sh` 来编译你的程序。\n\n```shell\ng++ -std=gnu++17 -O2 -o grader grader.cpp ancient2.cpp\n```\n\n当编译成功时，会生成一个可执行文件 `grader`。\n\n请注意，实际的交互器和样例不同。样例交互器会作为单进程运行，即它会从标准输入中读取输入数据，并输出结果到标准输出。"},{"iden":"input","content":"第一行一个整数 $N$。\n\n第二行一个长为 $N$ 的字符串 $S$。"},{"iden":"output","content":"样例交互器会输出如下内容到标准输出。\n\n- 如果你的程序被判为正确，它会输出 `Query` 函数中参数 `m` 的最大值，如 `Accepted: 22`。然而，如果你的程序没有调用 `Query` 函数并被判为正确，它会输出 `Accepted: 0`。\n- 如果你的程序被判为任一类的答案错误，样例交互器会输出其类别，如 `Wrong Answer [4]`。\n\n如果程序满足多种答案错误的类别，样例交互器只会输出其中一个。"},{"iden":"note","content":"**【样例解释】**\n\n样例函数调用如下。\n\n| 对 `Solve` 的调用 |   返回值   |           对 `Query` 的调用            |    返回值     |\n| :---------------: | :--------: | :------------------------------------: | :-----------: |\n|    `Solve(3)`     |            |                              |               |\n|                   |   | `Query(4, [3, 3, 2, 2], [2, 2, 1, 0])` |      `3`      |\n|          |            |       `Query(2, [0, 1], [1, 0])`       |      `0`      |\n|                   |   |          `Query(1, [0], [0])`          | `0`  |\n|          |            |    `Query(3, [1, 1, 1], [1, 1, 1])`    |      `1`      |\n|                   |  `\"110\"`   |                                        |   |\n\n假设写在石板上的字符串 $S$ 是 `110`。如果我们把石板放在机器上，输入 $(m,a,b)=(4,[3,3,2,2],[2,2,1,0])$ 并做一次查询，机器将按如下方式操作。\n\n1. 机器将内存区域置为 $0$。\n2. 对于第一次操作，因为 $S_0$ 是 `1`，机器会将内存区域置为 $b_0$，即 $2$。\n3. 对于第二次操作，因为 $S_1$ 是 `1`，机器会将内存区域置为 $b_2$，即 $1$。\n4. 对于第三次操作，因为 $S_2$ 是 `0`，机器会将内存区域置为 $a_1$，即 $3$。\n5. 因为最终内存区域被置为的整数是 $3$，所以机器显示 $3$。\n\n注意这组样例输入不满足限制 $N=1\\ 000$。在文件中，`sample-02.txt` 满足这个限制。\n\n**【数据范围】**\n\n对于全部数据，满足：\n\n- $N=1\\ 000$\n- $S$ 是一个长为 $N$ 的字符串\n- $S$ 中的每个字符要么是 `0`，要么是 `1`\n\n对于每组数据，实际的交互器 **不是**适应性的。这意味着交互器在开始时答案就已经确定了。\n\n如果你的程序在任意一组数据上被判为任意一种答案错误，在本题你将获得 $0$ 分。\n\n如果你的程序在所有数据上都被判为正确，你的分数由 $M$ 确定，其中 $M$ 是所有数据的 `Query` 函数中参数 `m` 的最大值。然而，如果你的程序没有调用 `Query` 函数并且被判为正确，你的分数由 $M=0$ 确定。\n\n- 如果 $103\\le M\\le 1\\ 002$，你的得分为 $10+\\lfloor \\frac{(1002-M)^2}{9000}\\rfloor$\n- 如果 $0\\le M\\le 102$，你将获得 $100$ 分。\n\n这里 $\\lfloor x\\rfloor$ 表示不超过 $x$ 的最大整数。"}],"translated_statement":null,"sample_group":[["3\n110","Accepted: 4"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}