← 返回题目列表

Codeforces · 2209/C

C. 找到零

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

这是一个交互问题。

给你一个整数$$$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$$$,答案是正确的。