CF2150E2 Hidden Single (Version 2)

[AdhesiveWombat - Overdrive](https://soundcloud.com/adhesivewombat/adhesivewombat-overdrive) ⠀ 本题有两个版本，它们对 $t$、$n$ 以及最大查询次数有不同要求，解出其中一个版本不一定能解出另一个。你可能需要阅读两个版本。两种版本都禁止 hack。 这是一道交互题。 有一个隐藏数组 $a_1, a_2, \ldots, a_{2n-1}$，其中包含了 $1$ 到 $n$ 所有的数。每个数都恰好出现两次，只有一个数只出现一次。 你可以进行如下格式的查询，其中 $S$ 是 $ \{1, 2, \ldots, 2n-1\} $ 的一个子集，$x$ 是区间 $[1, n]$ 内的整数： - $\texttt{ask(S, x)}$：是否存在 $i \in S$，使得 $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$ 次查询。 若要发起查询，请输出一行格式为 `? 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$，应立即退出程序。 若要输出最终答案，请打印 `! y`，其中 $y$ 是那个恰好出现一次的数字。输出答案不计入查询次数。 更多细节请参阅交互示例。 如果你发起的查询次数过多、查询格式错误，或者给出的答案错误，你将得到 Wrong answer（答案错误）的结果。 在打印查询语句后，请务必输出换行符并刷新输出缓冲区。否则，你将得到 Idleness limit exceeded（超出空闲限制）的结果。具体操作如下： - C++：使用 `fflush(stdout)` 或 `cout.flush()`； - Java：使用 `System.out.flush()`； - Pascal：使用 `flush(output)`； - Python：使用 `stdout.flush()`； 其他语言请参考相应文档。 请注意，交互器‌非自适应‌（non-adaptive），这意味着隐藏的数据数组不依赖于你所发起的查询。

无

在第一个测试用例中，$n = 300$，所以隐藏数组长度为 $2n-1 = 599$。 |#|选手输出|交互器回复|说明| |-|-------|---------|---| |1|? 187 1 1| 0|查询：$a_1=187$？否。| |2|! 187||我们猜答案是 $187$。幸运的是答案正确。| 我们总共询问了 1 次（输出答案不计入查询次数），小于最多允许的 $925$ 次查询数。 由 ChatGPT 5 翻译