Universal Cup Judging System

Universal Cup

Time Limit: 1.0 s Memory Limit: 256 MB Total points: 100 Interactive
Statistics

这是一个交互式题目。在打印每一行后,请务必刷新输出缓冲区。在 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

样例交互器不保证与官方交互器行为完全一致。然而,官方交互器也不是自适应的。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.