这两个版本对 $$$t$$$、$$$n$$$ 和最大查询数有不同的约束,解决两个版本之一不一定能解决另一个版本。您可能想阅读这两个版本。两个版本都禁用了黑客攻击。
这是一个交互问题。
有一个隐藏数组 $$$a_1, a_2, \ldots, a_{2n-1}$$$ 包含从 $$$1$$$ 到 $$$n$$$ 的所有数字,除了一个(只出现一次)之外,所有数字都出现了两次。
您可以按以下格式提出查询,其中 $$$S$$$ 是 $$$\{1, 2, \ldots, 2n-1\}$$$ 的子集,$$$x$$$ 是 $$$[1, n]$$$ 中的整数:
- $$$\texttt{ask(S, x)}$$$: S$$$中是否存在$$$i \使得$$$a_i = x$$$?
最多使用 $$$4n + 2 \lceil \log_2 n \rceil$$$ 查询查找只出现一次的数字。你不需要找到它的位置。
请注意,交互器是 不 自适应,这意味着隐藏数组不依赖于您进行的查询。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 4000$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 300$$$) - 隐藏数组 $$$a_1, a_2, \ldots, a_{2n-1}$$$ 中的最大值。
保证所有测试用例的 $$$n^2$$$ 总和不超过 $$$4 \cdot 10^5$$$。
这个问题总共有 $$$80$$$ 测试(包括示例)。
互动
对于每个测试用例,首先读取单个整数 $$$n$$$。如果你读到的整数是$$$-1$$$,则说明前面的测试用例的答案是错误的,你应该立即退出。
在每个测试用例中,您最多可以询问 $$$4n + 2 \lceil \log_2 n \rceil$$$ 查询。
要提出查询,请以 $$$\texttt{? 格式打印一行x|S| S_1 S_2 ... S_|S|}$$$ 与 $$$1 \leq x \leq n$$$、$$$1 \leq S_1、S_2、\ldots、S_{|S|} \leq 2n-1$$$ 以及所有不同的 $$$S_i$$$。
作为对查询的响应,如果答案为“是”,您将获得 $$$1$$$;如果答案为“否”,您将获得 $$$0$$$;如果您进行了无效查询,则将获得 $$$-1$$$。如果您收到 $$$-1$$$,您应该立即退出。
要输出答案,您应该打印 $$$\texttt{! y}$$$,其中 $$$y$$$ 是只出现一次的数字。打印答案不算作查询。
请参阅交互示例以更清楚地了解。
如果您提出太多查询、提出格式错误的查询或您的答案错误,您将得到 $$$\texttt{错误答案}$$$。
打印查询后,不要忘记输出行尾并刷新输出。否则,您将得到$$$\texttt{超出空闲限制}$$$。为此,请使用:
- $$$\texttt{fflush(stdout)}$$$ 或 $$$\texttt{cout.flush()}$$$ 在 C++ 中;
- $$$\texttt{System.out.flush()}$$$ 在 Java 中;
- $$$\texttt{flush(output)}$$$ 帕斯卡;
- $$$\texttt{stdout.flush()}$$$ 在 Python 中;
- 请参阅其他语言的文档。
请注意,交互器是 不 自适应,这意味着隐藏数组不依赖于您进行的查询。
示例
输入复制
2 2 0 3 1 1 1 1
输出复制
? 1 2 1 2 ! 1 ? 1 2 1 4 ? 2 2 1 4 ? 2 1 2 ? 1 1 5 ! 3
注意
在第一个测试用例中,$$$n = 2$$$,因此隐藏数组的长度为$$$2n-1 = 3$$$。与交互一致的一种可能的隐藏数组是 $$$[2, 2, 1]$$$,其中 $$$1$$$ 出现一次,$$$2$$$ 出现两次。
| # | 参赛者打印 | 互动者回复 | 说明 |
| 1 | ? 1 2 1 2 | 0 | 查询:$$$a_1=1$$$还是$$$a_2=1$$$?不(它们都是 $$$2$$$)。因此$$$1$$$最多只能出现一次(仅出现在$$$3$$$位置),因此恰好出现一次的数字必定是$$$1$$$。 |
| 2 | ! 1 | 输出答案。 |
我们提出了 $$$1$$$ 查询(打印答案不算是查询),该查询小于允许的最大查询数 ($$$4n + 2 \lceil \log_2 n \rceil = 10$$$)。
$$$\颜色{白色}{2}$$$
在第二个测试用例中,$$$n = 3$$$,因此隐藏数组的长度为$$$5$$$。与交互一致的一种可能的隐藏数组是 $$$[1, 2, 3, 2, 1]$$$,其中 $$$3$$$ 出现一次,$$$1$$$ 和 $$$2$$$ 出现两次。
| # | 参赛者打印 | 互动者回复 | 说明 |
| 1 | ? 1 2 1 4 | 1 | 检查 $$$a_1$$$ 或 $$$a_4$$$ 是否等于 $$$1$$$。是的($$$a_1=1$$$)。 |
| 2 | ? 2 2 1 4 | 1 | 检查 $$$a_1$$$ 或 $$$a_4$$$ 是否等于 $$$2$$$。是的($$$a_4=2$$$)。 |
| 3 | ? 2 1 2 | 1 | 检查是否$$$a_2=2$$$。是的。 |
| 4 | ? 1 1 5 | 1 | 检查是否$$$a_5=1$$$。是的。 |
| 5 | ! 3 | 我们知道$$$3$$$既不能出现在位置$$$1$$$和$$$4$$$(其中按某种顺序包含$$$1$$$和$$$2$$$),也不能出现在位置$$$2$$$和$$$5$$$(分别包含$$$2$$$和$$$1$$$)。所以答案一定是$$$3$$$。 |