← 返回题目列表

Codeforces · 1365/G

G. 安全密码

中文机器翻译题面 查看原题

这是一个交互问题。

Ayush 设计了另一种方案来设置他的锁的密码。该锁有 $$$n$$$ 个槽,每个槽可以容纳任何非负整数。密码 $$$P$$$ 是 $$$n$$$ 整数的序列,其中第 $$$i$$$ 个元素放入锁的第 $$$i$$$ 个槽中。

为了设置密码,Ayush 提出了一个由 $$$n$$$ 整数组成的数组 $$$A$$$,每个整数都在 $$$[0, 2^{63}-1]$$$ 范围内。然后,他将 $$$P$$$ 的第 $$$i$$$ 个元素设置为数组中除 $$$A_i$$$ 之外的所有整数的按位或。

您需要猜测密码。要进行查询,您可以选择数组索引的非空子集,并要求对数组中具有该子集中索引的所有元素进行按位或运算。您最多可以提出 13 个疑问。

输入

输入的第一行包含一个整数 $$$n$$$ $$$(2 \le n \le 1000)$$$ — 锁中的槽数。

互动

要询问查询,请打印一行:

- 在开头打印“? c”(不带引号),其中 $$$c$$$ $$$(1 \leq c \leq n)$$$ 表示正在查询的索引子集的大小,后跟 $$$c$$$ 范围 $$$[1, n]$$$ 中的不同空格分隔整数。

对于每个查询,您将收到一个整数 $$$x$$$ — 数组中所有查询索引中的值的按位或。如果查询的索引子集无效或者超出了查询数量,那么您将得到 $$$x = -1$$$。在这种情况下,您应该立即终止该程序。

当您猜出密码后,打印一行“!”(不带引号),后跟 $$$n$$$ 空格分隔的整数 - 密码序列。

猜测密码不会计入询问的查询次数。

交互器不具有自适应性。数组 $$$A$$$ 不会随查询而改变。

打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

黑客

要破解该解决方案,请使用以下测试格式:

在第一行打印一个整数 $$$n$$$ $$$(2 \le n \le 1000)$$$ - 锁中的槽数。下一行应包含 $$$n$$$ 范围内以空格分隔的整数 $$$[0, 2^{63} - 1]$$$ — 数组 $$$A$$$。

示例

输入 #1

3

1

2

4

输出 #1

? 1 1

? 1 2

? 1 3

! 6 5 3

注意

示例中的数组 $$$A$$$ 为 $$$\{{1, 2, 4\}}$$$。密码的第一个元素是 $$$A_2$$$ 和 $$$A_3$$$ 的按位或,第二个元素是 $$$A_1$$$ 和 $$$A_3$$$ 的按位或,第三个元素是 $$$A_1$$$ 和 $$$A_2$$$ 的按位或。因此,密码序列为 $$$\{{6, 5, 3\}}$$$。