这是一个交互问题。
给你一个整数$$$n$$$。有一个长度为 $$$2n$$$ 的隐藏数组 $$$a$$$。出现从 $$$1$$$ 到 $$$n$$$ 的每个整数 正好一次 在$$$a$$$。其余元素都是$$$0$$$。
您可以进行以下类型的查询:
- 选择两个整数 $$$i$$$ 和 $$$j$$$ ($$$1 \le i,j \le 2n$$$, $$$i \ne j$$$)。如果$$$a_i=a_j$$$,法官将回应$$$1$$$,否则回应$$$0$$$。
在不超过 $$$n+1$$$ 查询中查找任意整数 $$$k$$$ ($$$1 \le k \le 2n$$$),使得 $$$a_k=0$$$ 。请注意,交互器是 自适应,这意味着隐藏数组 $$$a$$$ 可能会根据您的查询而变化,但不会与之前的查询相矛盾。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^4$$$)。隐藏数组 $$$a$$$ 的长度将为 $$$2n$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^4$$$。
互动
要进行查询,请按以下格式输出一行:
- $$$\texttt{?}\;i\;j$$$ ($$$1 \le i,j \le 2n$$$, $$$i \ne j$$$)
作为对查询的响应,您将得到:
- $$$1$$$ 如果 $$$a_i=a_j$$$;
- $$$0$$$ 如果 $$$a_i \ne a_j$$$;
- $$$-1$$$ 如果您进行了无效查询或超出了 $$$n+1$$$ 查询限制。
要报告答案,请按以下格式输出一行:
- $$$\texttt{!}\;k$$$ ($$$1 \le k \le 2n$$$)
此后,继续进行下一个测试用例,或者如果这是最后一个测试用例则终止。
请注意,报告答案不计入 $$$n+1$$$ 查询。
交互器是 自适应。这意味着隐藏数组 $$$a$$$ 可能会根据您的查询而变化,但不会与之前的查询相矛盾。
打印每个查询后,不要忘记输出行尾并刷新$$$^{\text{*}}$$$ 输出。否则,你会得到 超出空闲限制 判决。如果在任何交互步骤中您读取 $$$-1$$$ 而不是有效数据,则您的解决方案必须立即退出。这意味着您的解决方案将收到 错误答案 由于无效查询或任何其他错误。未能退出可能会导致任意判决,因为您的解决方案将继续从关闭的流中读取。
对于这个问题,黑客被禁用。
$$$^{\text{*}}$$$要刷新,请使用:
- fflush(标准输出) or cout.flush() 在 C++ 中;
- sys.stdout.flush() 在 Python 中;
- 请参阅其他语言的文档。
示例
输入复制
2 2 0 1 3 1 0 0
输出复制
? 1 2 ? 3 1 ! 3 ? 5 6 ? 2 4 ? 1 3 ! 6
注意
在第一个示例测试用例中,隐藏数组 $$$a$$$ 是 $$$[0,1,0,2]$$$:
- 在第一个查询中,$$$(i,j)=(1,2)$$$。由于$$$a_1=0$$$, $$$a_2=1$$$, $$$a_1 \ne a_2$$$,法官回应$$$0$$$。
- 在第二个查询中,$$$(i,j)=(3,1)$$$。由于$$$a_3=0$$$、$$$a_1=0$$$、$$$a_3 = a_1$$$,因此法官回应$$$1$$$。
- 程序报告 $$$k=3$$$ 作为答案。由于 $$$a_3=0$$$,答案是正确的。
在第二个示例测试用例中,隐藏数组 $$$a$$$ 为 $$$[3,2,0,1,0,0]$$$:
- 在第一个查询中,$$$(i,j)=(5,6)$$$。由于$$$a_5=0$$$、$$$a_6=0$$$、$$$a_5 = a_6$$$,因此法官回应$$$1$$$。
- 在第二个查询中,$$$(i,j)=(2,4)$$$。由于$$$a_2=2$$$, $$$a_4=1$$$, $$$a_2 \ne a_4$$$,法官回应$$$0$$$。
- 在第三个查询中,$$$(i,j)=(1,3)$$$。由于$$$a_1=3$$$,$$$a_3=0$$$,$$$a_1 \ne a_3$$$,法官回应$$$0$$$。
- 程序报告 $$$k=6$$$ 作为答案。由于 $$$a_6=0$$$,答案是正确的。