CF2156D.Find the Last Number

这是一个交互题。

有一个长度为 $n$ 的隐藏排列 $p$。你可以通过以下方式与它进行最多 $2n$ 次的交互：

• 选择两个整数 $i$ 和 $x$，其中 $1\le i\le n-1$ 且 $1\le x\le 10^9$。裁判会返回 $\mathtt{0}$ ，如果 $p_i\,\&\,x$ 等于 $0$；否则返回 $\mathtt{1}$。

重要提示：你不能对最后一个元素 $p_n$ 进行提问（因为 $i\le n-1$）。

你的目标是在最多 $2n$ 次查询内确定排列的最后一个元素 $p_n$ 的值。

注意，交互器是非自适应的。这意味着隐藏排列 $p$ 在开始时就已经固定，并不会因为你的查询而改变。

一个长度为 $n$ 的排列是由 $n$ 个 $1$ 到 $n$ 的不同整数组成的数组，排列顺序任意。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（$2$ 出现了两次），$[1,3,4]$ 也不是排列（$n=3$ 但其中有 $4$）。

$\&$ 表示按位与运算。

每个测试点包含多组测试数据。第一行包含一个整数 $t$ （$1\le t\le 10^3$），表示测试数据组数。

每组测试数据的第一行包含一个整数 $n$（$2\leq n\leq 2\cdot 10^4$），表示排列 $p$ 的长度。

对于每一组测试数据，在读入 $n$ 后，你应开始与交互器交互，并在继续下一组测试数据前输出答案。

保证所有测试数据中 $n$ 的总和不超过 $2\cdot 10^4$。

（本题为交互题，具体格式请结合题目内容。）

在第一个测试中，交互过程如下。

SolutionJuryExplanation
$\texttt{2}$ 表示有 2 组测试数据。
$\texttt{2}$ 第一组测试数据中，隐藏排列为 $[2,1]$（长度为 $2$）。
$\texttt{? 1 1}$ $\texttt{0}$
选手询问 $p_1\,\&\,1$。由于 $p_1 = 2$ 且 $2\,\&\,1 = 0$，因此裁判返回 $0$。

$\texttt{? 1 2}$ $\texttt{1}$
选手询问 $p_1\,\&\,2$。由于 $p_1 = 2$ 且 $2\,\&\,2 = 2$，因此裁判返回 $1$。

$\texttt{! 1}$
选手确定最后一个元素为 $1$，因为通过前面的查询已知第一个元素不是 $1$。

$\texttt{3}$ 第二组测试数据，隐藏排列为 $[1,3,2]$（长度为 $3$）。
$\texttt{? 1 3}$ $\texttt{1}$
选手询问 $p_1\,\&\,3$。由于 $p_1 = 1$ 且 $1\,\&\,3 = 1$，因此裁判返回 $1$。

$\texttt{? 1 2}$ $\texttt{0}$
选手询问 $p_1\,\&\,2$。由于 $p_1 = 1$ 且 $1\,\&\,2 = 0$，因此裁判返回 $0$。

$\texttt{? 2 3}$ $\texttt{1}$
选手询问 $p_2\,\&\,3$。由于 $p_2 = 3$ 且 $3\,\&\,3 = 3$，因此裁判返回 $1$。

$\texttt{! 2}$
选手确定最后一个元素为 $2$。

请注意，示例输入输出中的空行仅为便于阅读，实际交互时不会出现。

由 ChatGPT 5 翻译