题目背景

译自 JOI Open 2023 T1 「古代の機械 2 / Ancient Machine 2」

这是一道交互题。

在提交本题前请务必仔细阅读以下内容。

本题只支持 C++ 语言提交（建议使用 C++14，请不要使用 C++14 (GCC9)）。

由于洛谷特殊的交互机制，在提交本题时，请去掉代码中的 #include "ancient2.h" 语句，并将添加以下语句粘贴到代码最开头：

int Query(int m, std::vector<int> a, std::vector<int> 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<int> a, std::vector<int> 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 来编译你的程序。

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]。

如果程序满足多种答案错误的类别，样例交互器只会输出其中一个。

3
110

Accepted: 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])
		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$ 的最大整数。