当前没有测试数据。

题目描述

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

Bitaro 和 Bibako 是挖掘和调查 JOI 王国废墟的考古学家。在废墟中，Bitaro 发现了一块古老的石板，Bibako 发现了一台古老的机器。

从研究结果中，Bitaro 发现石板上写有一个长为 $N$ 的字符串 $S$。字符串中每个字符要么是 $0$，要么是 $1$。然而，他还不知道字符串 $S$ 中的每个字符是什么。

另一方面，从研究结果中，Bibako 弄清了如何使用机器。为了使用它，需要将石板放在机器上，输入一个整数 $m$ 和两个整数序列 $a,b$，然后做一次查询。这里整数 $m$ 和整数序列 $a,b$ 需满足如下条件：

1. 整数 $m$ 在 $1$ 和 $1002$ 之间（包括两端）。
2. 序列 $a$ 和 $b$ 的长度均为 $m$。
3. 序列 $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 想要确定石板上写的字符串。但机器十分脆弱，查询次数不能超过 $1000$ 次，且输入机器的整数 $m$ 的最大值需要越小越好。

实现细节

你需要在程序一开始使用预处理指令 #include 引入库 ancient2.h，它应实现如下函数：

• std::string Solve(int N)：每组测试数据中仅被调用一次，需返回与石板上字符串 $S$ 相同的字符串。
  • 参数 $N$：表示石板上字符串 $S$ 的长度 $N$。
  • 返回要求：
    1. 长度必须为 $N$，否则被判为 Wrong Answer [1]。
    2. 每个字符只能是 $0$ 或 $1$，否则被判为 Wrong Answer [2]。
    3. 必须与 $S$ 完全相同，否则被判为 Wrong Answer [3]。

你的程序可以调用如下函数：

• int Query(int m, std::vector<int> a, std::vector<int> b)：用于发起一次查询。
  • 参数说明：
    1. $m$：输入机器的整数 $m$，需在 $1$ 到 $1002$ 之间（包括两端），否则被判为 Wrong Answer [4]。
    2. $a,b$：输入机器的两个整数序列，长度均需等于 $m$，否则被判为 Wrong Answer [5]。
    3. $a,b$ 中元素需在 $0$ 到 $m-1$ 之间（包括两端），否则被判为 Wrong Answer [6]。
  • 返回值：机器最终显示的整数。
  • 调用限制：次数不能超过 $1000$ 次，否则被判为 Wrong Answer [7]。

注意事项

1. 程序可实现其他内部函数或使用全局变量。
2. 禁止使用标准输入输出，禁止与其他文件通信，但可将调试信息输出到标准错误输出。

编译和测试运行

可在「附加文件」下载样例 grader 测试程序，需将 grader.cpp、ancient2.cpp 和 ancient2.h 放在同一文件夹，编译命令如下（或运行 compile.sh）：

g++ -std=gnu++17 -O2 -o grader grader.cpp ancient2.cpp

编译成功后生成可执行文件 grader。

样例交互器输入

样例交互器从标准输入读取：

1. 第一行：整数 $N$。
2. 第二行：长为 $N$ 的字符串 $S$。

样例交互器输出

1. 若正确：输出 Query 函数中参数 $m$ 的最大值，如 Accepted: 22；若未调用 Query 且正确，输出 Accepted: 0。
2. 若错误：输出错误类别，如 Wrong Answer [4]；若满足多种错误类别，仅输出其中一种。

数据范围与提示

1. 全部数据满足：$N=1000$，$S$ 是长为 $N$ 的 $01$ 字符串。
2. 实际交互器非适应性，即答案在开始时已确定。
3. 评分规则：
   • 若任意一组数据被判错误，本题得 $0$ 分。
   • 若所有数据正确，分数由 $M$（所有数据 Query 中 $m$ 的最大值）确定：
     • 若 $0\le M\le 102$，得 $100$ 分。
     • 若 $103\le M\le 1002$，得分为 $10+\lfloor \frac{(1002-M)^2}{9000}\rfloor$（$\lfloor x\rfloor$ 表示不超过 $x$ 的最大整数）。

样例交互

假设石板上字符串 $S$ 是 110（$N=3$），样例函数调用如下：

对 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

样例 Query 过程（以 Query(4, [3,3,2,2], [2,2,1,0]) 为例）

1. 机器初始内存为 $0$。
2. 第 $1$ 次操作（$i=0$，$S_0=1$）：内存置为 $b_0=2$。
3. 第 $2$ 次操作（$i=1$，$S_1=1$）：内存置为 $b_2=1$。
4. 第 $3$ 次操作（$i=2$，$S_2=0$）：内存置为 $a_1=3$。
5. 最终内存为 $3$，故返回 $3$。

注：该样例输入不满足 $N=1000$，满足限制的样例见文件 sample-02.txt。