这是一个交互问题。
有一个秘密序列 $$$a_1, a_2, \ldots, a_{2n-1},a_{2n}$$$,其中包含从 $$$1$$$ 到 $$$n$$$ 的每个整数 正好两次.
您的任务是通过使用以下类型的查询来猜测序列:
- "? $$$k\;j_1\;j_2\;\ldots\;j_k$$$" — 选择整数 $$$k$$$ ($$$1 \le k \le 2n$$$) 和 $$$k$$$ 不同 索引 $$$j_1, j_2, \ldots, j_k$$$ ($$$1 \le j_1 , j_2 , \ldots , j_k \le 2n$$$)。作为对查询的回应,陪审团将返回 $$$\text{MAD}([a_{j_1}, a_{j_2}, \ldots, a_{j_k}])$$$。
我们将整数序列的 $$$\operatorname{MAD}$$$ (Maximum Appearing Duplicate) 定义为至少出现两次的最大整数。具体来说,如果没有至少出现两次的数字,则 $$$\operatorname{MAD}$$$ 值为 $$$0$$$。一些示例如下:
- $$$\操作员名称{MAD}([1, 2, 1]) = 1$$$;
- $$$\操作员名称{MAD}([2, 2, 3, 3]) = 3$$$;
- $$$\操作员名称{MAD}([1, 2, 3, 4]) = 0$$$。
请识别秘密序列 最多使用 $$$3n$$$ 查询.
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 3000$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 300$$$)。
保证所有测试用例的$$$n^2$$$总和不超过$$$10^5$$$。
阅读此行输入后,交互将从您的第一个查询开始。
互动
要进行查询,请按以下格式输出一行(不带引号):
- "? $$$k\;j_1\;j_2\;\ldots\;j_k$$$" ($$$1 \le k \le 2n$$$, $$$1 \le j_1 , j_2 , \ldots , j_k \le 2n$$$)
这里,您选择的索引 $$$j_1 , j_2 , \ldots , j_k$$$ 必须是 成对不同.
然后,在每次查询后,读取一个整数——查询的答案。
您最多可以进行 $$$3n$$$ 这种类型的查询。
如果您的程序找到了序列 $$$a$$$,请按以下格式打印该行(不带引号):
- "! $$$a_1\;a_2\;\ldots\;a_{2n-1}\;a_{2n}$$$" ($$$1 \le a_i \le n$$$)
请注意,这不计入查询限制。
此后,继续进行下一个测试用例,如果这是最后一个测试用例,则退出。
此任务中的交互器是 不自适应。换句话说,序列 $$$a$$$ 在交互过程中不会改变。
如果您在交互过程中进行超过 $$$3n$$$ 查询,您的程序必须立即终止,并且您将收到 错误答案 判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。
打印每一行后,不要忘记输出行尾并刷新输出缓冲区。否则,您将收到 超出空闲限制 判决。要冲洗,请使用:
- fflush(标准输出) or cout.flush() 在 C++ 中;
- System.out.flush() ;
- stdout.flush() 在 Python 中;
- 请参阅其他语言的文档。
黑客
要进行破解,请使用以下格式:
第一行应包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 3000$$$)。
每个测试用例的第一行应包含一个整数 $$$n$$$ ($$$2 \leq n \leq 300$$$)。
以下行应包含 $$$2n$$$ 整数 $$$a_1,a_2,\ldots,a_{2n}$$$ ($$$1 \leq a_i \leq n$$$)。从 $$$1$$$ 到 $$$n$$$ 的每个数字必须恰好出现两次。
所有测试用例的 $$$n^2$$$ 总和不应超过 $$$10^5$$$。
例如,示例交互对应的hack格式如下。
2
2
2 2 1 1
2
1 2 1 2
示例
输入复制
2 2 2 0 1 2 0 1 1
输出复制
? 2 2 1 ? 2 1 3 ? 3 1 3 4 ! 2 2 1 1 ? 2 1 2 ? 2 1 3 ? 3 1 3 4 ! 1 2 1 2
注意
在第一个测试用例中,隐藏序列是 $$$a=[2,2,1,1]$$$。
对于查询“? 2 2 1”,陪审团返回 $$$2$$$,因为 $$$\operatorname{MAD}([a_2, a_1]) = \operatorname{MAD}([2, 2]) = 2$$$。
对于查询“? 2 1 3”,陪审团返回 $$$0$$$,因为 $$$\operatorname{MAD}([a_1, a_3]) = \operatorname{MAD}([2, 1]) = 0$$$。
对于查询“? 3 1 3 4”,陪审团返回 $$$1$$$,因为 $$$\operatorname{MAD}([a_1, a_3, a_4]) = \operatorname{MAD}([2 ,1, 1]) = 1$$$。
请注意,示例交互仅用于理解语句,并且不 不 保证找到唯一的序列$$$a$$$。