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