← 返回题目列表

Codeforces · 1299/E

E. 太卑鄙了

中文机器翻译题面 查看原题

这个问题是交互式的。

我们向您隐藏了从 $$$1$$$ 到 $$$n$$$ 的数字排列 $$$p_1, p_2, \dots, p_n$$$,其中 $$$n$$$ 是偶数。您可以尝试使用以下查询来猜测它:

$$$?$$$ $$$k$$$ $$$a_1$$$ $$$a_2$$$ $$$\点$$$ $$$a_k$$$。

作为响应,您将了解索引为 $$$a_1, a_2, \dots, a_k$$$ 的元素的平均值是否为整数。换句话说,如果 $$$\frac{p_{a_1} + p_{a_2} + \dots + p_{a_k}}{k}$$$ 为整数,则您将收到 $$$1$$$,否则为 $$$0$$$。

你必须猜测排列。您可以提出不超过 $$$18n$$$ 的查询。

请注意,排列 $$$[p_1, p_2, \dots, p_k]$$$ 和 $$$[n + 1 - p_1, n + 1 - p_2, \dots, n + 1 - p_k]$$$ 是无法区分的。因此,您可以保证 $$$p_1 \le \frac{n}{2}$$$。

请注意,排列 $$$p$$$ 在交互开始之前是固定的,并且不取决于您的查询。换句话说,交互器不具有适应性。

请注意,您不必最小化查询数量。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 800$$$,$$$n$$$ 是偶数)。

互动

您通过阅读 $$$n$$$ 开始交互。

在单独的行输出中询问有关位置 $$$a_1, a_2, \dots, a_k$$$ 上的元素的问题

$$$?$$$ $$$k$$$ $$$a_1$$$ $$$a_2$$$ ... $$$a_k$$$

查询中的数字必须满足 $$$1 \le a_i \le n$$$,并且所有 $$$a_i$$$ 必须不同。不要忘记“冲洗”以获得答案。

作为响应,如果 $$$\frac{p_{a_1} + p_{a_2} + \dots + p_{a_k}}{k}$$$ 为整数,则您将收到 $$$1$$$,否则为 $$$0$$$。

如果您的查询无效或您提出的查询超过 $$$18n$$$ 查询,程序将打印 $$$-1$$$ 并完成交互。您将收到错误答案判决。确保立即退出,以避免得到其他判决。

当确定排列时,输出

$$$!$$$ $$$p_1$$$ $$$p_2$$$ ... $$$p_n$$$

打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

黑客格式

对于 hacks,请使用以下格式:

第一行必须包含单个整数 $$$n$$$ ($$$2 \le n \le 800$$$,$$$n$$$ 是偶数)。

在下一行中输出 $$$n$$$ 整数 $$$p_1, p_2, \dots, p_n$$$ - 从 $$$1$$$ 到 $$$n$$$ 的数字的有效排列。 $$$p_1 \le \frac{n}{2}$$$ 必须成立。

示例

输入 #1

2
1 2

输出 #1

? 1 2
? 1 1
! 1 2