Description

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无法直接判断哪些房间亮着灯，但她至少能知道尖叫的总次数。也就是说，她能知道游乐车经过了多少次“亮房间 $\leftrightarrow$ 暗房间”的切换。

你能帮 Erika 在老板发现前，找出哪两个开关分别控制首尾两个房间的灯吗？你最多可以进行 30 次游乐实验。

交互说明

本题为交互题。

• 程序首先读入一行整数 $N$，表示黑暗游乐项目的房间数。
• 然后，程序与评测器交互。每次你想发起一次游乐实验时，应输出一行以问号 "?" 开头，后跟一个长度为 $N$ 的 01 字符串，表示你打开了哪些开关（1 表示打开，0 表示关闭）。随后，程序应读入一个整数 $\ell$（$0 \leq \ell < N$），表示 Erika 听到的尖叫次数。
• 当你想输出最终答案时，输出一行以感叹号 "!" 开头，后接两个整数 $A$ 和 $B$（$0 \leq A, B < N$）。这两个数必须是控制首尾两个房间灯的开关编号，顺序不限。输出答案后，程序应立即退出。

评测器是非自适应的，即隐藏数组 $p$ 在交互开始前就已确定。

每次游乐实验后请确保立即刷新标准输出，否则可能被判为超时。在 Python 中，使用 input() 读取输入时会自动刷新；C++ 中可以用 cout << endl; 或 fflush(stdout) 手动刷新。

Input Format

见交互说明。

Output Format

见交互说明。

5

3

3

? 10001

? 10110

! 2 4

3

0

2

0

? 111

? 110

? 000

! 1 0

4

3

? 1010

! 0 3

Hint

样例说明

在第一个样例中，隐藏排列为 $[p_0, p_1, p_2, p_3, p_4] = [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。接着，程序请求另一次游乐，打开了第 0、2、3 号开关，点亮了 $p_0, p_2, p_3$ 号房间，也有 3 次尖叫。最后，程序输出 $A = 2$ 和 $B = 4$，即这两个开关分别控制首尾两个房间（$p_2 = 0$，$p_4 = 4$）。注意，$A = 4, B = 2$ 也是正确答案。

在第二个样例中，隐藏排列为 $[p_0, p_1, p_2] = [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$ 都是正确答案。

在第三个样例中，隐藏排列为 $[p_0, p_1, p_2, p_3] = [0, 1, 2, 3]$，符合测试组 2、3、4、5、6 的约束。注意本例仅做一次游乐实验，实际上不一定能唯一推断出答案，但样例解答猜对了。

测试工具

为方便测试，官方提供了一个简单的工具。见题目页面底部的“attachments”。该工具为可选项，正式评测器与此工具略有不同。

使用方法：准备一个输入文件（如 "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

约束与评分

• $3 \leq N \leq 30000$
• 最多可进行 30 次游乐实验（输出最终答案不计入次数）。超出此限制将被判为 Wrong Answer。

你的解答将在一组测试组上进行评测，每组有若干测试用例。要获得该测试组的分数，你需要通过该测试组的所有测试用例。

翻译由 ChatGPT-4.1 完成。