题目描述

Erika 最近在波恩附近的 Phantasialand 游乐园找到了一份暑期工作。她被雇佣来控制黑暗之旅经过的房间中的灯光。

该旅程经过 $N$ 个房间，编号从 $0$ 到 $N-1$。房间按顺序遍历，从房间 $0$ 开始，到房间 $N-1$ 结束。房间中的灯光由 $N$ 个开关控制（同样编号从 $0$ 到 $N-1$），每个房间对应一个开关。开关 $s$（其中 $0 \leq s < N$）控制房间 $p_{s}$ 的灯光。

Erika 的老板要求她打开第一个和最后一个房间的灯，并关闭其他所有房间的灯。听起来很简单，对吧？她只需要打开两个开关 $A$ 和 $B$，使得 $p_{A}=0$ 和 $p_{B}=N-1$（或者 $p_{B}=0$ 和 $p_{A}=N-1$）。不幸的是，Erika 在老板描述控制方法时没有完全注意，她不记得数组 $p$——即哪个开关控制哪个房间。

Erika 需要在老板发现之前弄清楚这一点。在每次旅程开始前，Erika 会关闭所有灯光，然后可以选择打开一部分开关。随着旅程从一个房间到另一个房间，每当旅程从一个亮着的房间到暗着的房间或反过来时，Erika 会听到乘客兴奋的尖叫声。旅程的速度可能会有所不同，因此 Erika 无法直接推断出哪些房间是亮着的，但她至少能听到尖叫的次数。也就是说，她会知道旅程从亮到暗或从暗到亮的次数。

你能帮助 Erika 在老板发现之前弄清楚哪两个开关控制第一个和最后一个房间的灯光吗？你最多可以使用 $30$ 次旅程。

交互方式

这是一个交互式问题。

• 你的程序应首先读取一行包含整数 $N$：黑暗之旅中的房间数量。
• 然后，你的程序应与交互器交互。要开始一次旅程，你应输出一行以问号 ? 开头，然后是一个长度为 $N$ 的字符串，由 $0$（关闭）和 $1$（打开）组成，表示你如何设置 $N$ 个开关。然后，你的程序应读取一个整数 $\ell$ $(0 \leq \ell < N)$，即 Erika 听到的乘客尖叫次数。
• 当你想要回答时，输出一行以感叹号 ! 开头，后面跟着两个整数 $A$ 和 $B$ $(0 \leq A, B < N)$。为了让你的答案被接受，这必须是控制两个端点房间的开关的编号，顺序不限。之后，你的程序应退出。

交互器是非自适应的，这意味着隐藏数组 $p$ 在交互开始前就已确定。

请确保在每次旅程后刷新标准输出，否则你的程序可能会被判定为超时。在 Python 中，只要使用 input() 读取行，输出会自动刷新。在 C++ 中，cout << endl; 除了输出换行外还会刷新；如果使用 printf，请使用 fflush(stdout)。

测试工具

为了方便测试你的解决方案，我们提供了一个简单的工具供下载。请参见「文件」页面。你可以选择是否使用该工具。请注意，评测时使用的交互器与提供的测试工具有所不同。

要使用该工具，创建一个输入文件，例如 sample1.in，文件应以数字 $N$ 开头，紧接着一行指定隐藏的排列 $p_{0}, p_{1}, \ldots, p_{N-1}$。例如：

5
2 1 0 3 4

对于 Python 程序，例如 solution.py（通常以 pypy3 solution.py 运行），运行：

python3 testing_tool.py pypy3 solution.py < sample1.in

对于 C++ 程序，首先编译它（例如使用 g++ -g -O2 -std=gnu++23 -static solution.cpp -o solution.out），然后运行：

python3 testing_tool.py ./solution.out < sample1.in

样例 1

交互器输出	你的输出
5
	? 10001
3
	? 10110
3
	! 2 4

在第一个样例中，隐藏的排列为 $\left[p_{0}, p_{1}, p_{2}, p_{3}, p_{4}\right]=[2, 1, 0, 3, 4]$。这满足子任务 $2, 5, 6$ 的限制条件。首先，程序读取整数 $N=5$。然后，程序请求一次旅程，打开两个开关：开关 $4$ 和开关 $0$。这控制房间 $p_{4}=4$ 和 $p_{0}=2$；见下图所示。Erika 听到 3 次尖叫（图中以箭头标记）：第一次是从未亮的房间 $1$ 到亮的房间 $2$；第二次是从亮的房间 $2$ 到未亮的房间 $3$；第三次是从未亮的房间 $3$ 到亮的房间 $4$。程序随后请求另一次旅程，房间 $p_{0}, p_{2}, p_{3}$ 是亮的，Erika 听到 $3$ 次尖叫。最后，程序以 $A=2$ 和 $B=4$ 作答，这确实是正确的，因为它们控制第一个和最后一个房间（$p_{2}=0$ 和 $p_{4}=4$）。请注意，$A=4$ 和 $B=2$ 也是正确的答案。

样例 2

交互器输出	你的输出
3
	? 111
0
	? 110
2
	? 000
0
	! 1 0

在第二个样例中，隐藏的排列为 $\left[p_{0}, p_{1}, p_{2}\right]=[2, 0, 1]$。这满足子任务 $1, 2, 5, 6$ 的限制条件。程序请求一次旅程，打开所有三个开关。由于这意味着所有房间都是亮的，Erika 不会听到尖叫声。在第二次旅程中，开关 $1$ 和 $0$ 被打开，使得房间 $p_{1}=0$ 和 $p_{0}=2$ 是亮的，而房间 $1$ 是暗的。Erika 听到两次尖叫：当旅程从房间 $0$（亮）到房间 $1$（暗），以及从房间 $1$（暗）到房间 $2$（亮）时。在最后一次旅程中，没有开关被打开，意味着所有三个房间都是暗的，Erika 再次没有听到尖叫声。程序随后以开关 $1$ 和 $0$ 作答，这确实控制第一个和最后一个房间。! 0 1 和 ! 1 0 都是可接受的答案。

样例 3

交互器输出	你的输出
4
	? 1010
3
	! 0 3

在第三个样例中，隐藏的排列为 $\left[p_{0}, p_{1}, p_{2}, p_{3}\right]=[0, 1, 2, 3]$。这满足子任务 $2, 3, 4, 5, 6$ 的限制条件。请注意，在这次旅程后不一定能推断出答案，但样例解决方案猜对了答案并很幸运。

数据范围与提示

对于所有输入数据，满足：

• $3 \leq N \leq 30000$。
• 你最多可以发起 $30$ 次旅程（输出最终答案不计入旅程次数）。如果你超过这个限制，将得到判为「Wrong Answer」。

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$9$	$N=3$
$2$	$15$	$N \leq 30$
$3$	$17$	$p_{0}=0$，即开关 $0$ 控制房间 $0$
$4$	$16$	$N$ 是偶数，一个端点房间的开关在前半部分 $(0 \leq A < \frac{N}{2}$)，另一个在后半部分 ($\frac{N}{2} \leq B < N$)
$5$	$14$	$N \leq 1000$
$6$	$29$	无附加限制