← 返回题目列表

Codeforces · 1583/D

D. 奥姆卡和生命的意义

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

原来,生命的意义是整数$$$1, 2, \ldots, n$$$的排列$$$p_1, p_2, \ldots, p_n$$$ ($$$2 \leq n \leq 100$$$)。奥姆卡(Omkar)创造了所有生命,知道这种排列,并允许您使用一些查询来找出它。

查询由 $$$a_1, a_2, \ldots, a_n$$$ 之间的整数数组 $$$1$$$ 和 $$$n$$$ 组成。 $$$a$$$ 不需要是排列。 Omkar 将首先计算 $$$a$$$ 和 $$$p$$$ 的两两求和,这意味着他将计算一个数组 $$$s$$$,其中 $$$s_j = p_j + a_j$$$ 对于所有 $$$j = 1, 2, \ldots, n$$$。然后,他会找到最小的索引$$$k$$$,使得$$$s_k$$$在$$$s$$$中出现多次,并用$$$k$$$回答。如果没有这样的索引$$$k$$$,那么他会回答$$$0$$$。

您最多可以执行 $$$2n$$$ 查询。弄清楚生命的意义$$$p$$$。

互动

通过读取单个整数 $$$n$$$ ($$$2 \leq n \leq 100$$$) 开始交互 - 排列 $$$p$$$ 的长度。

然后您可以进行查询。查询由单行“$$$? \enspace a_1 \enspace a_2 \enspace \ldots \enspace a_n$$$” ($$$1 \leq a_j \leq n$$$) 组成。

每个查询的答案将是如上所述的单个整数 $$$k$$$ ($$$0 \leq k \leq n$$$)。

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

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

要输出你的答案,请打印一行“$$$! \enspace p_1 \enspace p_2 \enspace \ldots \enspace p_n$$$”,然后终止。

您最多可以进行 $$$2n$$$ 查询。输出答案不算作查询。

黑客格式

要破解,首先输出一行包含 $$$n$$$ ($$$2 \leq n \leq 100$$$),然后输出另一行包含从 $$$1$$$ 到 $$$n$$$ 的数字的隐藏排列 $$$p_1, p_2, \ldots, p_n$$$。

示例

输入 #1

5

2

0

1

输出 #1

? 4 4 2 3 2

? 3 5 1 5 5

? 5 2 4 3 1

! 3 2 1 5 4

注意

在示例中,隐藏排列 $$$p$$$ 为 $$$[3, 2, 1, 5, 4]$$$。提出了三个询问。

第一个查询是 $$$a = [4, 4, 2, 3, 2]$$$。得出 $$$s = [3 + 4, 2 + 4, 1 + 2, 5 + 3, 4 + 2] = [7, 6, 3, 8, 6]$$$。 $$$6$$$ 是唯一出现多次的数字,它首先出现在索引 $$$2$$$ 处,从而成为查询 $$$2$$$ 的答案。

第二个查询是 $$$a = [3, 5, 1, 5, 5]$$$。得出 $$$s = [3 + 3, 2 + 5, 1 + 1, 5 + 5, 4 + 5] = [6, 7, 2, 10, 9]$$$。这里没有出现多次的数字,因此查询的答案是 $$$0$$$。

第三个查询是 $$$a = [5, 2, 4, 3, 1]$$$。得出 $$$s = [3 + 5, 2 + 2, 1 + 4, 5 + 3, 4 + 1] = [8, 4, 5, 8, 5]$$$。 $$$5$$$ 和 $$$8$$$ 在这里都出现了不止一次。 $$$5$$$ 首先出现在索引 $$$3$$$ 处,而 $$$8$$$ 首先出现在索引 $$$1$$$ 处,并且 $$$1 < 3$$$,从而得到查询 $$$1$$$ 的答案。

请注意,该示例仅旨在提供交互如何工作的示例;不能保证上述查询代表确定答案的正确策略。