← 返回题目列表

Codeforces · 2219/B2

B2. 独特的价值(困难版)

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

简易版和困难版之间的区别在于允许的最大查询数。在这个版本中,它是 33。

有一个秘密数组$$$a$$$,长度为$$$2n+1$$$,其元素为从$$$1$$$到$$$n$$$的整数。每个值恰好出现两次,但有一个值恰好出现三次。

您的目标是找到出现三次的值的三个位置。

为此,您最多可以询问以下查询 33 次:

  1. 选择一个整数 $$$k$$$ 和一个数组 $$$s$$$,其中包含 $$$1$$$ 和 $$$2n+1$$$ 之间的 $$$k$$$ 不同索引。
  2. 您将收到 $$$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$$$。

在每个测试用例中您最多可以提出 $$$33$$$ 查询。

要提出查询,请按以下格式打印一行:

  • ? $$$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}$$$ 中仅出现一次的不同值的数量,或者换句话说,即不重复的值的计数。

如果您的程序对一个测试用例进行超过 $$$33$$$ 查询,或者进行无效查询,则对该查询的响应将为 $$$-1$$$。收到这样的响应后,你的程序应该立即终止以接收判决 错误答案。否则,它可能会收到任何其他判决。

当您确定当前测试用例的答案时,打印

  • ! $$$x$$$$$$y$$$$$$z$$$

其中$$$x、y、z$$$ 是在$$$a$$$ 中出现三次的值的三个不同索引。您可以按任何顺序打印索引。

请注意,此输出不计入 $$$33$$$ 的查询限制。

之后,继续下一个测试用例,或者如果没有更多的测试用例,则终止程序。

打印每个查询后,不要忘记输出行尾并刷新*输出。否则,您将得到 超出空闲限制 判决。

如果在任何交互步骤中您读取 $$$-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。