← 返回题目列表

Codeforces · 1534/E

E. 阵列丢失

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

这是一个交互问题。

注意:数组 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) 的异或和定义为 $$$a_1 \oplus a_2 \oplus \ldots \oplus a_n$$$,其中 $$$\oplus$$$ 表示按位异或运算。

Little Dormi 在圣诞节收到了一组 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$。然而,在寒假期间玩它时,他不小心将它掉进了他的异或机器中,导致阵列丢失了。

XOR 机器当前配置的查询大小为 $$$k$$$(您无法更改),并允许您执行以下类型的查询:通过为机器提供 $$$k$$$ 不同索引 $$$x_1, x_2, \ldots, x_k$$$,它将输出 $$$a_{x_1} \oplus a_{x_2} \oplus \ldots \oplus a_{x_k}$$$。

作为小多米的哥哥,你想通过查询异或机来帮助他恢复数组 $$$a_1, a_2, \ldots, a_n$$$ 的异或和。

小多米不太有耐心,所以为了尽可能快,你必须查询异或机最少次数才能找到他的数组的异或和。形式上,令 $$$d$$$ 为查找任何长度为 $$$n$$$ 且查询大小为 $$$k$$$ 的数组的异或和所需的最少查询数。如果您在最多 $$$d$$$ 查询中找到正确的异或和,您的程序将被接受。

最后,您还注意到,对于机器 $$$k$$$ 的某些配置和 $$$n$$$ 的值,可能无法恢复 Little Dormi 丢失数组的异或和。如果是这种情况,您也应该报告。

数组 $$$a_1, a_2, \ldots, a_n$$$ 在开始查询 XOR 机器之前是固定的,并且不会随着查询而改变。

输入

唯一的输入行包含整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 500$$$, $$$1 \le k \le n$$$)、丢失数组的长度和 XOR 机的配置查询大小。

原始数组的元素满足 $$$1 \le a_i \le 10^9$$$。

可以证明,如果可以在给定约束下恢复 XOR 和,则最多可以在 $$$500$$$ 查询中完成。也就是说,$$$d \le 500$$$。

拿走$$$n$$$和$$$k$$$后,开始互动。

互动

每个查询均以“? b”格式进行,其中 $$$b$$$ 是一个由 $$$k$$$ 个不同整数组成的数组,从 $$$1$$$ 到 $$$n$$$ 表示丢失数组中要查询异或和的元素的索引。

然后您将收到一个整数$$$x$$$,即查询元素的异或和。可以证明 $$$0 \le x \le 2 \cdot 10^9$$$ 永远为真。

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

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

如果您在任何时候进行无效查询或尝试进行超过 $$$500$$$ 查询(这是硬限制),则交互将立即终止,并给出错误答案判决。请注意,如果您超过 $$$d$$$ 查询,交互将正常继续,除非您也超过 $$$500$$$ 查询硬限制,但无论如何您仍然会收到错误答案判决。

黑客

要破解解决方案,请使用以下格式。

第一行包含整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 500$$$, $$$1 \le k \le n$$$)。

第二行包含数组 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。

输出

如果无法恢复数组的异或和,则在取出 $$$n$$$ 和 $$$k$$$ 后立即输出 $$$-1$$$。不要开始互动。

否则,当您的程序找到丢失数组 $$$a_1, a_2, \ldots, a_n$$$ 的异或和时,请按以下格式报告答案:"! x",其中 $$$x$$$ 是数组 $$$a_1, a_2, \ldots, a_n$$$ 的异或和,并在刷新输出流后立即正常终止程序。

请注意,回答不算作查询。

示例

输入 #1

5 3

4

0

1

输出 #1

? 1 2 3

? 2 3 5

? 4 1 5

! 7

输入 #2

3 2

输出 #2

-1

注意

在第一个示例交互中,数组 $$$a_1, a_2, \ldots, a_n$$$ 为 $$$2, 1, 7, 5, 6$$$,其异或和为 $$$7$$$。

第一个查询要求索引 $$$1,2,3$$$,因此响应为 $$$a_1 \oplus a_2 \oplus a_3 = 2 \oplus 1 \oplus 7 = 4$$$。

第二个查询要求索引 $$$2,3,5$$$,因此响应为 $$$a_2 \oplus a_3 \o​​plus a_5 = 1 \oplus 7 \oplus 6 = 0$$$。

第三个查询要求索引 $$$4,1,5$$$,因此响应为 $$$a_4 \oplus a_1 \oplus a_5 = 5 \oplus 2 \oplus 6 = 1$$$。请注意,索引可以按任何顺序输出。

此外,尽管示例交互中进行了三个查询,但这只是为了演示交互格式,并不一定代表最佳策略。

在第二个示例交互中,无论查询什么都无法恢复Little Dormi数组的异或和,因此程序立即输出$$$-1$$$并退出。