CF2150E2.Hidden Single (Version 2)

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$。

null

在第一个测试用例中，$n = 300$，所以隐藏数组长度为 $2n-1 = 599$。

#	选手输出	交互器回复	说明
1	? 187 1 1	0	查询：$a_1=187$？否。
2	! 187		我们猜答案是 $187$。幸运的是答案正确。
我们总共询问了 1 次（输出答案不计入查询次数），小于最多允许的 $925$ 次查询数。

由 ChatGPT 5 翻译