← 返回题目列表

Codeforces · 1364/E

E. 异或

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

这是一个交互问题!

Ehab 有一个长度为 $$$n$$$ 的隐藏排列 $$$p$$$,由从 $$$0$$$ 到 $$$n-1$$$ 的元素组成。出于某种原因,你想弄清楚排列。为此,您可以为 Ehab $$$2$$$ 提供不同的索引 $$$i$$$ 和 $$$j$$$,他将回复 $$$(p_i|p_j)$$$,其中 $$$|$$$ 是按位或运算。

Ehab 有足够的空闲时间来回答 $$$4269$$$ 问题,虽然他可以回答这么多问题,但他懒得玩你的愚蠢游戏,所以他会提前修复排列,并且不会根据你的查询进行更改。你能猜出排列吗?

输入

唯一一行包含整数 $$$n$$$ $$$(3 \le n \le 2048)$$$ — 排列的长度。

互动

要提出问题,请打印“?$$$i$$$ $$$j$$$”(不带引号,$$$i \neq j$$$)然后,您应该阅读答案,即$$$(p_i|p_j)$$$。

如果我们回答 $$$-1$$$ 而不是有效答案,则意味着您超出了查询数量或进行了无效查询。

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

要打印答案,请打印“! $$$p_1$$$ $$$p_2$$$ $$$\ldots$$$ $$$p_n$$$”(不带引号)。请注意,回答不算作 $$$4269$$$ 查询之一。

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

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

黑客:

第一行应包含整数 $$$n$$$ ($$$3 \le n \le 2^{11}$$$) — 排列 $$$p$$$ 的长度。

第二行应包含 $$$n$$$ 以空格分隔的整数 $$$p_1$$$、$$$p_2$$$、$$$\ldots$$$、$$$p_n$$$ ($$$0 \le p_i < n$$$) — 排列 $$$p$$$ 的元素。

示例

输入 #1

3
1
3
2

输出 #1

? 1 2
? 1 3
? 2 3
! 1 0 2

注意

在第一个示例中,排列为 $$$[1,0,2]$$$。您首先询问 $$$p_1|p_2$$$,Ehab 回复 $$$1$$$。然后您询问 $$$p_1|p_3$$$,Ehab 回复 $$$3$$$。最后,您询问 $$$p_2|p_3$$$,Ehab 回复 $$$2$$$。然后你猜测排列。