← 返回题目列表

Codeforces · 2150/E2

E2. 隐藏单曲(版本2)

中文机器翻译题面 查看原题
AdhesiveWombat - 超速档
⠀

这两个版本对 $$$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 10查询:$$$a_1=187$$$吗?不。
2! 187我们感到很幸运,并声称答案是 $$$187$$$。幸运的是,答案是正确的。

我们提出了$$$1$$$查询(打印答案不算是查询),该查询小于允许的最大查询数($$$925$$$)。