简单版和困难版之间的区别是允许的最大查询数。在这个版本中,它是66。
有一个秘密数组$$$a$$$,长度为$$$2n+1$$$,其元素为从$$$1$$$到$$$n$$$的整数。每个值恰好出现两次,但有一个值恰好出现三次。
您的目标是找到出现三次的值的三个位置。
为此,您最多可以询问以下查询 66 次:
- 选择一个整数 $$$k$$$ 和一个数组 $$$s$$$,其中包含 $$$1$$$ 和 $$$2n+1$$$ 之间的 $$$k$$$ 不同索引。
- 您将收到 $$$a_{s_1}, a_{s_2}, \ldots, a_{s_k}$$$ 中恰好出现一次的不同值的数量,或者换句话说,即不重复值的计数。
例如,如果值 $$$a_{s_1}、\ldots、a_{s_k}$$$ 为 $$$\{2, 1, 2, 3, 2, 3, 6, 7\}$$$,则查询的答案将为 3,因为 1、6、7 是唯一出现一次的值。 3出现了2次,2出现了3次,都不止一次了,所以不计算在内。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 1000$$$)。
数组 $$$a$$$ 对于测试用例来说是固定的,并且在交互过程中不会改变。换句话说,交互者是 不自适应.
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^4$$$。
互动
对于每个测试用例,首先读取单个整数 $$$n$$$。
在每个测试用例中您最多可以提出 $$$66$$$ 查询。
要提出查询,请按以下格式打印一行:
- ? $$$k$$$ $$$s_1$$$ $$$s_2$$$ $$$\ldots$$$ $$$s_k$$$ ($$$s_i \neq s_j$$$ 对于 $$$i \neq j$$$, $$$1 \le s_i \le 2 \cdot n + 1$$$)
作为对查询的响应,您将收到 $$$a_{s_1}、a_{s_2}、\ldots、a_{s_k}$$$ 中仅出现一次的不同值的数量,或者换句话说,即不重复的值的计数。
如果您的程序对一个测试用例进行超过 $$$66$$$ 查询,或者进行无效查询,则对该查询的响应将为 $$$-1$$$。收到这样的响应后,你的程序应该立即终止以接收判决 错误答案。否则,它可能会收到任何其他判决。
当您确定当前测试用例的答案时,打印
- ! $$$x$$$$$$y$$$$$$z$$$
其中$$$x、y、z$$$ 是在$$$a$$$ 中出现三次的值的不同三个索引。您可以按任何顺序打印索引。
请注意,此输出不计入 $$$66$$$ 的查询限制。
之后,继续下一个测试用例,或者如果没有更多的测试用例,则终止程序。
打印每个查询后,不要忘记输出行尾并刷新*输出。否则,您将得到 超出空闲限制 判决。
如果在任何交互步骤中您读取 $$$-1$$$ 而不是有效数据,您的解决方案必须立即退出。这意味着您的解决方案将收到 错误答案 由于无效查询或任何其他错误。未能退出可能会导致任意判决,因为您的解决方案将继续从关闭的流中读取。
请注意,交互器是 不自适应,这意味着 $$$a$$$ 在整个交互过程中保持不变。
黑客
要进行破解,请使用以下格式。
第一行应包含一个整数 $$$t$$$ $$$(1 \le t \le 500)$$$,测试用例的数量。
每个测试用例的第一行应包含 $$$n$$$ $$$(2 \le n \le 1000)$$$。
每个测试用例的第二行应该包含一个长度为 $$$2 \cdot n + 1$$$ 的数组,即数组 $$$a$$$,它应该满足问题的约束。
所有测试用例的 $$$n$$$ 总和不应超过 $$$2 \cdot 10^4$$$。
示例
输入复制
1 2 0 2 2 0 1
输出复制
? 2 1 2 ? 2 1 4 ? 2 1 5 ? 5 1 2 3 4 5 ? 4 1 2 3 4 ! 1 2 3
注意
秘密数组是 $$$a = [1, 1, 1, 2, 2]$$$。
在第一个查询中,我们询问 $$$[a_1, a_2] = [1, 1]$$$ 中恰好出现一次的值的数量,因为值 1 重复,所以答案为 0。
在第二个查询中,我们询问 $$$[a_1, a_4] = [1, 2]$$$ 中只出现一次的值的数量,因为值 1 和 2 只出现一次,所以答案是 2。
在第四个查询中,我们要求 $$$[a_1, a_2, a_3, a_4, a_5] = [1, 1, 1, 2, 2]$$$ 中恰好出现一次的值的数量,因为值 1 和 2 重复,所以答案为 0。
最后,我们打印出重复 3 次的值的索引为 1、2 和 3。