← 返回题目列表

Codeforces · 1407/C

C. 巧克力兔子

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

这是一个交互问题。

我们向您隐藏了长度为 $$$n$$$ 的排列 $$$p$$$,由从 $$$1$$$ 到 $$$n$$$ 的元素组成。你想猜一下。为此,您可以给我们 2 个不同的索引 $$$i$$$ 和 $$$j$$$,我们将回复 $$$p_{i} \bmod p_{j}$$$ ($$$p_{i}$$$ 除以 $$$p_{j}$$$ 的余数)。

我们有足够的耐心来回答最多 $$$2 \cdot n$$$ 查询,因此您应该符合此限制。你能做到吗?

提醒一下,长度 $$$n$$$ 的排列是一个由 $$$n$$$ 不同整数组成的数组,从 $$$1$$$ 到 $$$n$$$ 以任意顺序排列。例如,$$$[2,3,1,5,4]$$$ 是一个排列,但 $$$[1,2,2]$$$ 不是排列($$$2$$$ 在数组中出现两次),$$$[1,3,4]$$$ 也不是排列($$$n=3$$$ 但数组中有 $$$4$$$)。

输入

输入的唯一行包含单个整数 $$$n$$$ ($$$1 \le n \le 10^4$$$) — 排列的长度。

互动

交互从读取 $$$n$$$ 开始。

那么你最多可以通过以下方式进行 $$$2 \cdot n$$$ 查询:

- “?x y”($$$1 \le x,y \le n,x \ne y$$$)。

在每一个之后,您应该读取一个整数 $$$k$$$,它等于 $$$p_x \bmod p_y$$$。

当您猜出排列后,打印一行“!”(不带引号),后跟数组 $$$p$$$ 并退出。

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

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

收到“-1”后立即退出,您将看到错误的答案判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。

黑客格式

在第一行输出 $$$n$$$ ($$$1 \le n \le 10^4$$$)。在第二行中打印 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ 的排列。

示例

输入 #1

3

1

2

1

0

输出 #1

? 1 2

? 3 2

? 1 3

? 2 1

! 1 3 2