这是一个交互式题目。在打印每一行后,请务必刷新输出缓冲区。在 C++ 中可以使用 cout << flush,在 Java 中可以使用 System.out.flush(),在 Python 中可以使用 sys.stdout.flush()。你必须严格遵守“交互协议”部分的说明,否则可能会收到“答案错误”(Wrong Answer)、“超出时间限制”(Time Limit Exceeded)或其他判决。
既然所有的任务都以神话中的矮人为主角,那么考虑一些实际的东西或许是值得的。
有一个长度为 $N$ 的隐藏序列 $A$,其中的元素均为 $[0, 2^N - 1]$ 范围内的整数。你的任务是通过有限次数的查询来恢复它。在每次查询中,你提供一个长度为 $N$ 的序列 $B$,其元素也在 $[0, 2^N - 1]$ 范围内。响应计算如下:
- 创建序列 $C$,其中 $C$ 的第 $i$ 个元素是 $A$ 的第 $i$ 个元素与 $B$ 的第 $i$ 个元素的按位异或(bitwise xor)。我们用 $\oplus$ 表示异或。
- 集合 $S$ 由 $C$ 中元素的任意子集异或和所能构成的所有值组成。特别地,空集的异或和为 $0$。
- 查询的答案为 $|S|$。
例如,如果 $A = (1, 4, 3)$ 且 $B = (0, 4, 7)$,则 $C = (1 \oplus 0, 4 \oplus 4, 3 \oplus 7) = (1, 0, 4)$,且 $S = \{0, 1, 4, 5\}$,因此答案为 $4$。
两个数 $x$ 和 $y$ 的按位异或在第 $i$ 位为 $1$ 当且仅当 $x$ 和 $y$ 在第 $i$ 位的值不同。例如,$5 \oplus 3 = (101)_2 \oplus (011)_2 = (110)_2 = 6$。在 C++ 和 Python 中,异或运算符为 ^。
交互协议
序列 $A$ 在开始时是固定的,不依赖于所做的查询。
首先,读取一行,包含一个整数 $1 \le N \le 60$。然后你可以进行查询。
要进行查询,打印一行,包含 ? 后跟 $N$ 个 $[0, 2^N - 1]$ 范围内的整数。作为响应,读取一个整数作为答案。
准备好后,打印 ! 后跟隐藏序列的 $N$ 个整数。然后你的程序应立即退出,无需进一步输出。
请记住在每次查询后以及写入答案后刷新缓冲区。在数字与 ?、! 符号之间留出空格。
样例
输入格式 1
3 4 8
输出格式 1
? 1 2 3 ? 0 0 0 ! 1 3 4
说明
第一个样例测试中 $N = 3$ 且 $A = (1, 3, 4)$:
| 输入 | 输出 | 说明 |
|---|---|---|
| 3 | $N = 3$ | |
| ? 1 2 3 | $B = (1, 2, 3)$ | |
| 4 | $C = (1 \oplus 1, 3 \oplus 2, 4 \oplus 3) = (0, 1, 7)$,$S = \{0, 1, 6, 7\}$,故答案为 $4$ | |
| ? 0 0 0 | $B = (0, 0, 0)$ | |
| 8 | $C = (1 \oplus 0, 3 \oplus 0, 4 \oplus 0) = (1, 3, 4)$,$S = \{0, 1, \dots, 7\}$,故答案为 $8$ | |
| ! 1 3 4 | 隐藏序列为 $A = (1, 3, 4)$ |
本地测试
在“附件”部分,你可以找到 B.zip,其中包含样例测试和一个交互器 grader.cpp。要测试你的程序,请编译它,然后将测试名称和你的可执行文件传递给编译后的 ./grader:
./grader [test] [executable]
例如:./grader 0b.in ./abc
样例交互器不保证与官方交互器行为完全一致。然而,官方交互器也不是自适应的。