这是一个交互问题。
存在 $$$[0,1,2,\ldots,n-1]$$$ 的秘密排列 $$$p$$$。你的任务是找到 $$$2$$$ 索引 $$$x$$$ 和 $$$y$$$ ($$$1 \leq x, y \leq n$$$, 可能 $$$x=y$$$) 使得 $$$p_x=0$$$ 或 $$$p_y=0$$$。为了找到它,您最多可以提出 $$$2n$$$ 查询。
在一个查询中,您给出两个整数 $$$i$$$ 和 $$$j$$$ ($$$1 \leq i, j \leq n$$$, $$$i \neq j$$$) 并接收 $$$\gcd(p_i,p_j)^\dagger$$$ 的值。
请注意,排列 $$$p$$$ 在进行任何查询之前是固定的,并且不依赖于查询。
$$$^\dagger$$$ $$$\gcd(x, y)$$$ 表示整数 $$$x$$$ 和 $$$y$$$ 的最大公约数 (GCD)。请注意,$$$\gcd(x,0)=\gcd(0,x)=x$$$ 对于所有正整数 $$$x$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^4$$$)。
读取每个测试用例的整数 $$$n$$$ 后,您应该开始交互。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^4$$$。
互动
每个测试用例的交互从读取整数 $$$n$$$ 开始。
要进行查询,请输出“? $$$i$$$ $$$j$$$” ($$$1 \leq i, j \leq n$$$, $$$i \neq j$$$),不带引号。然后,您应该读取一个整数 - 您的查询 $$$\gcd(p_i,p_j)$$$ 的答案。在每个测试用例中您最多可以进行 $$$2n$$$ 这样的查询。
如果要打印答案,请输出“! $$$x$$$ $$$y$$$” ($$$1 \leq x, y \leq n$$$),不带引号。完成此操作后,读取 $$$1$$$ 或 $$$-1$$$。如果 $$$p_x=0$$$ 或 $$$p_y=0$$$,您将收到 $$$1$$$,否则您将收到 $$$-1$$$。如果您收到 $$$-1$$$,您的程序必须立即终止才能收到错误答案判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。
如果您收到整数 $$$-1$$$ 而不是答案或有效值 $$$n$$$,则意味着您的程序进行了无效查询,超出了查询限制,或者对之前的测试用例给出了错误答案。您的程序必须立即终止才能收到错误答案判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。
打印查询或答案后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
黑客
要破解,请使用以下格式。
第一行应包含单个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$)。
每个测试用例的第一行应包含一个整数 $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^4$$$)。
每个测试用例的第二行应包含 $$$n$$$ 空格分隔的整数 $$$p_1,p_2,\ldots,p_n$$$。 $$$p$$$ 应该是 $$$[0,1,2,\ldots,n-1]$$$ 的排列。
$$$n$$$ 的总和不应超过 $$$2 \cdot 10^4$$$。
示例
输入 #1
2 2 1 1 5 2 4 1
输出 #1
? 1 2 ! 1 2 ? 1 2 ? 2 3 ! 3 3
注意
在第一个测试中,交互进行如下。
SolutionJuryExplanation$$$\texttt{2}$$$有 2 个测试用例。$$$\texttt{2}$$$在第一个测试用例中,隐藏排列是 $$$[1,0]$$$,长度为 $$$2$$$。$$$\texttt{? 1 2}$$$$$$\texttt{1}$$$解决方案要求$$$\gcd(p_1,p_2)$$$,陪审团以$$$1$$$.$$$\texttt{! 1 2}$$$$$$\texttt{1}$$$解决方案知道 $$$p_1=0$$$ 或 $$$p_2=0$$$,并打印答案。由于输出正确,陪审团以 $$$1$$$ 响应并继续下一个测试用例。$$$\texttt{5}$$$在第二个测试用例中,隐藏排列为 $$$[2,4,0,1,3]$$$,长度为 $$$5$$$。$$$\texttt{? 1 2}$$$$$$\texttt{2}$$$解决方案要求$$$\gcd(p_1,p_2)$$$,陪审团回应$$$2$$$.$$$\texttt{? 2 3}$$$$$$\texttt{4}$$$解决方案要求$$$\gcd(p_2,p_3)$$$,陪审团回应$$$4$$$.$$$\texttt{! 3 3}$$$$$$\texttt{1}$$$解决方案以某种方式确定$$$p_3=0$$$,并打印答案。由于输出是正确的,陪审团以 $$$1$$$ 回应。
请注意,示例输入和输出中的空行是为了清楚起见,在实际交互中不会出现。
在每个测试用例之后,请确保阅读 $$$1$$$ 或 $$$-1$$$。