这两个版本对 $$$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$$$?
最多使用 $$$925$$$ 查询查找只出现一次的数字。你不需要找到它的位置。
请注意,交互器是 不 自适应,这意味着隐藏数组不依赖于您进行的查询。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 20$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$n = 300$$$) - 隐藏数组 $$$a_1, a_2, \ldots, a_{2n-1}$$$ 中的最大值。
这个问题(包括示例)总共有 $$$50$$$ 测试。该示例的 $$$t = 1$$$,所有其他测试的 $$$t = 20$$$。
互动
对于每个测试用例,首先读取单个整数 $$$n$$$。如果你读到的整数是$$$-1$$$,则说明前面的测试用例的答案是错误的,你应该立即退出。
在每个测试用例中您最多可以提出 $$$925$$$ 查询。
要提出查询,请以 $$$\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(输出)}$$$(帕斯卡);
- $$$\texttt{stdout.flush()}$$$ 在 Python 中;
- 请参阅其他语言的文档。
请注意,交互器是 不 自适应,这意味着隐藏数组不依赖于您进行的查询。
示例
输入复制
1 300 0
输出复制
? 187 1 1 ! 187
注意
在第一个测试用例中,$$$n = 300$$$,因此隐藏数组的长度为$$$2n-1 = 599$$$。
| # | 参赛者打印 | 互动者回复 | 说明 |
| 1 | ? 187 1 1 | 0 | 查询:$$$a_1=187$$$吗?不。 |
| 2 | ! 187 | 我们感到很幸运,并声称答案是 $$$187$$$。幸运的是,答案是正确的。 |
我们提出了$$$1$$$查询(打印答案不算是查询),该查询小于允许的最大查询数($$$925$$$)。