← 返回题目列表

Codeforces · 1270/D

D. 奇怪的装置

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

这个问题是交互式的。

我们隐藏了一个由 $$$n$$$ 成对不同数字组成的数组 $$$a$$$(这意味着没有两个数字相等)。您可以使用刚在 Amazon 上订购的新设备获取有关该阵列的一些信息。

该设备可以回答以下形式的查询:响应数组中$$$k$$$个不同元素的位置,按升序返回其中第$$$m$$$个的位置和值。

不幸的是,设备的说明书在交付过程中丢失了。然而,你记得$$$k$$$,但不记得$$$m$$$。您的任务是使用对此设备的查询来查找 $$$m$$$。

您最多可以提出 $$$n$$$ 个查询。

请注意,数组 $$$a$$$ 和数字 $$$m$$$ 在交互开始之前是固定的,不依赖于您的查询。换句话说,交互器不具有适应性。

请注意,您不必最小化查询数量,也不需要猜测数组 $$$a$$$。您只需猜测$$$m$$$。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1\le k < n \le 500$$$) - 数组的长度和查询中元素的数量。

保证数字$$$m$$$满足$$$1\le m \le k$$$,数组的元素$$$a_1,a_2,\dots,a_n$$$满足$$$0\le a_i \le 10^9$$$,且均不相同。

互动

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

在单独的行输出中询问有关位置 $$$x_1, x_2, \dots, x_k$$$ 上的元素的问题

$$$?$$$ $$$x_1$$$ $$$x_2$$$ $$$x_3$$$ ... $$$x_k$$$

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

作为响应,您将收到两个整数 $$$pos$$$ 和 $$$a_{pos}$$$ —— $$$a_{x_1}、a_{x_2}、\dots、a_{x_k}$$$ 中按升序排列的第 $$$m$$$ 个元素在数组 $$$a$$$ 中的位置,以及该位置上的元素。

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

当确定$$$m$$$时,输出

$$$!$$$ $$$米$$$

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

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

黑客格式

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

第一行必须包含三个整数 $$$n、k、m$$$ ($$$1 \le m \le k < n \le 500$$$) — 数组的长度、查询中的元素数量以及设备返回的升序编号。

在下一行中输出 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0\le a_i \le 10^9$$$) — 数组的元素。它们必须成对不同。

示例

输入 #1

4 3
4 9
4 9
4 9
1 2

输出 #1

? 2 3 4
? 1 3 4
? 1 2 4
? 1 2 3
! 3

注意

在示例中,$$$n = 4$$$、$$$k = 3$$$、$$$m = 3$$$、$$$a = [2, 0, 1, 9]$$$。