← 返回题目列表

Codeforces · 2150/E1

E1. 隐藏单曲(版本1)

中文机器翻译题面 查看原题
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$$$?

最多使用 $$$4n + 2 \lceil \log_2 n \rceil$$$ 查询查找只出现一次的数字。你不需要找到它的位置。

请注意,交互器是 不 自适应,这意味着隐藏数组不依赖于您进行的查询。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 4000$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 300$$$) - 隐藏数组 $$$a_1, a_2, \ldots, a_{2n-1}$$$ 中的最大值。

保证所有测试用例的 $$$n^2$$$ 总和不超过 $$$4 \cdot 10^5$$$。

这个问题总共有 $$$80$$$ 测试(包括示例)。

互动

对于每个测试用例,首先读取单个整数 $$$n$$$。如果你读到的整数是$$$-1$$$,则说明前面的测试用例的答案是错误的,你应该立即退出。

在每个测试用例中,您最多可以询问 $$$4n + 2 \lceil \log_2 n \rceil$$$ 查询。

要提出查询,请以 $$$\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(output)}$$$ 帕斯卡;
  • $$$\texttt{stdout.flush()}$$$ 在 Python 中;
  • 请参阅其他语言的文档。

请注意,交互器是 不 自适应,这意味着隐藏数组不依赖于您进行的查询。

示例

输入
复制

2
2

0

3

1

1

1

1

输出
复制


? 1 2 1 2

! 1

? 1 2 1 4

? 2 2 1 4

? 2 1 2

? 1 1 5

! 3

注意

在第一个测试用例中,$$$n = 2$$$,因此隐藏数组的长度为$$$2n-1 = 3$$$。与交互一致的一种可能的隐藏数组是 $$$[2, 2, 1]$$$,其中 $$$1$$$ 出现一次,$$$2$$$ 出现两次。

#参赛者打印互动者回复说明
1? 1 2 1 20查询:$$$a_1=1$$$还是$$$a_2=1$$$?不(它们都是 $$$2$$$)。因此$$$1$$$最多只能出现一次(仅出现在$$$3$$$位置),因此恰好出现一次的数字必定是$$$1$$$。
2! 1输出答案。

我们提出了 $$$1$$$ 查询(打印答案不算是查询),该查询小于允许的最大查询数 ($$$4n + 2 \lceil \log_2 n \rceil = 10$$$)。

$$$\颜色{白色}{2}$$$

在第二个测试用例中,$$$n = 3$$$,因此隐藏数组的长度为$$$5$$$。与交互一致的一种可能的隐藏数组是 $$$[1, 2, 3, 2, 1]$$$,其中 $$$3$$$ 出现一次,$$$1$$$ 和 $$$2$$$ 出现两次。

#参赛者打印互动者回复说明
1? 1 2 1 41检查 $$$a_1$$$ 或 $$$a_4$$$ 是否等于 $$$1$$$。是的($$$a_1=1$$$)。
2? 2 2 1 41检查 $$$a_1$$$ 或 $$$a_4$$$ 是否等于 $$$2$$$。是的($$$a_4=2$$$)。
3? 2 1 21检查是否$$$a_2=2$$$。是的。
4? 1 1 51检查是否$$$a_5=1$$$。是的。
5! 3我们知道$$$3$$$既不能出现在位置$$$1$$$和$$$4$$$(其中按某种顺序包含$$$1$$$和$$$2$$$),也不能出现在位置$$$2$$$和$$$5$$$(分别包含$$$2$$$和$$$1$$$)。所以答案一定是$$$3$$$。