这是一个交互问题。
Penchick 从澳大利亚黄金海岸度过一个宁静的假期回来,忘记给他的宠物鸭 Duong Canh 带回家的礼物!但也许在风景如画的海滩上经过深思熟虑而制作出的美丽问题可以成为完美的纪念品。
有一个隐藏的排列$$$^{\text{*}}$$$ $$$p$$$,长度为$$$n$$$,其中$$$n$$$ 是偶数。您可以进行以下查询:
- 选择排列$$$p$$$的子序列$$$^{\text{†}}$$$,长度为偶数$$$4\le k\le n$$$。交互器将返回所选子序列中两个中位数$$$^{\text{‡}}$$$的值。
使用最多 $$$80$$$ 查询查找排列 $$$p$$$ 中两个中位数的索引。
请注意,交互器是非自适应的。这意味着排列 $$$p$$$ 在开始时是固定的,不会根据您的查询而改变。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。
每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$6 \le n \le 100$$$,$$$n$$$ 是偶数)——隐藏排列 $$$p$$$ 的长度。
对于每个测试用例,在读取整数 $$$n$$$ 后,您应该开始交互并在读取下一个测试用例的 $$$n$$$ 之前找到答案。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^4$$$。
互动
要进行查询,请按以下格式打印一行:
- $$$\mathtt{?}\;k\;x_1\;x_2 \ldots x_{k-1}\;x_k$$$ ($$$4\le k\le n$$$, $$$k$$$ 是偶数, $$$1 \le x_i \le n$$$, $$$x_i$$$ 两两不同) — 所选长度子序列后跟所选子序列的索引。
每次查询后,您应该读取包含两个整数 $$$m_1$$$ 和 $$$m_2$$$ 的行 ($$$1 \le m_1 < m_2 \le n$$$) - 数组 $$$[p_{x_1}, p_{x_2}, \ldots, p_{x_{k-1}} 中两个中位数的值, p_{x_k}]$$$。
在每个测试用例中最多可以进行 $$$80$$$ 这样的查询。
要给出最终答案,请按以下格式打印一行:
- $$$\mathtt{!}\;i_1\;i_2$$$ ($$$1\le i_1, i_2 \le n$$$) — 两个中位数的索引。
请注意,$$$i_1$$$ 和 $$$i_2$$$ 的打印顺序并不重要。换句话说,只要 $$$p_{i_1} = \frac{n}{2}$$$ 和 $$$p_{i_2} = \frac{n}{2} + 1$$$ 或 $$$p_{i_1} = \frac{n}{2} + 1$$$ 和 $$$p_{i_2} = \frac{n}{2}$$$ 就有效。
打印每个查询后,不要忘记输出行尾并刷新$$$^{\text{*}}$$$ 输出。否则,您将得到超出空闲限制的判决。
如果在任何交互步骤中您读取 $$$-1$$$ 而不是有效数据,您的解决方案必须立即退出。这意味着您的解决方案将由于无效查询或任何其他错误而收到错误答案。未能退出可能会导致任意判决,因为您的解决方案将继续从关闭的流中读取。
黑客格式
对于 hack,请使用以下格式。
第一行应包含 $$$t$$$ — 测试用例的数量。
每个测试用例的第一行应包含一个偶数$$$n$$$。
每个测试用例的第二行应包含长度为 $$$n$$$ 的排列 $$$p_1, p_2, \ldots, p_n$$$。
例如,示例输入的 hack 格式为:
示例
输入 #1
2 6 3 4 3 4 2 3 10 3 4 6 7
输出 #1
? 6 1 2 3 4 5 6 ? 4 3 6 1 5 ? 4 3 6 2 5 ! 3 6 ? 6 1 3 7 8 9 10 ? 8 1 2 3 4 5 6 7 8 ! 6 5
注意
在第一个测试用例中,隐藏排列是 $$$p = [6, 2, 3, 5, 1, 4]$$$。
1. 为第一个查询选择了整个排列。整个排列 $$$p$$$ 的两个中位数是 $$$3$$$ 和 $$$4$$$。
2. 第二个查询中所选子序列的索引为 $$$3$$$、$$$6$$$、$$$1$$$ 和 $$$5$$$。交互器返回子序列 $$$[p_3, p_6, p_1, p_5] = [3, 4, 6, 1]$$$ 的两个中位数,即 $$$3$$$ 和 $$$4$$$。
3. 第二个查询中所选子序列的索引为 $$$3$$$、$$$6$$$、$$$2$$$ 和 $$$5$$$。交互器返回子序列 $$$[p_3, p_6, p_2, p_5] = [3, 4, 2, 1]$$$ 的两个中位数,即 $$$2$$$ 和 $$$3$$$。
答案“! 3 6”有效,因为 $$$p_3 = 3$$$ 且 $$$p_6 = 4$$$。
在第二个测试用例中,隐藏排列为 $$$p = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]$$$。
1. 第二个查询中所选子序列的索引为 $$$1$$$、$$$3$$$、$$$7$$$、$$$8$$$、$$$9$$$ 和 $$$10$$$。交互器返回子序列 $$$[p_1, p_3, p_7, p_8, p_9, p_{10}] = [10, 8, 4, 3, 2, 1]$$$ 的两个中位数,即 $$$3$$$ 和 $$$4$$$。
2. 第二个查询中所选子序列的索引为 $$$1$$$、$$$2$$$、$$$3$$$、$$$4$$$、$$$5$$$、$$$6$$$、$$$7$$$ 和 $$$8$$$。交互器返回子序列 $$$[p_1, p_2, p_3, p_4, p_5, p_6, p_7, p_8] = [10, 9, 8, 7, 6, 5, 4, 3]$$$ 的两个中位数,即 $$$6$$$ 和 $$$7$$$。
答案“! 5 6”有效,因为 $$$p_5 = 6$$$ 且 $$$p_6 = 5$$$。