这是一个交互问题。
陪审团隐藏了从 0 到 n - 1 的整数排列 p。你只知道长度 n。请记住,在排列中,所有整数都是不同的。
令 b 为 p 的逆排列,即对于所有 i,pbi = i。您唯一能做的就是对元素 pi 和 bj 进行异或,打印两个索引 i 和 j(不一定不同)。使用索引 i 和 j 进行查询的结果是,您将得到值 $$p_i \oplus b_j$$,其中 $$\bigcirc$$ 表示异或运算。异或运算的说明可以在注释中找到。
请注意,即使您进行所有可能的 n2 查询,某些排列仍可能与隐藏排列无法区分。您必须计算与隐藏排列无法区分的排列数量,并打印此类排列之一,进行不超过 2n 次查询。
隐藏的排列不取决于您的查询。
输入
第一行包含单个整数 n (1 ≤ n ≤ 5000) — 隐藏排列的长度。您应该首先读取这个整数。
互动
要询问两个元素的异或,请打印字符串“? i j”,其中 i 和 j — 是从 0 到 n - 1 的整数 — 排列元素的索引以及您想要知道其异或和的逆排列元素的索引。之后打印换行符并进行刷新操作。
打印查询后,您的程序应该读取单个整数 - $$p_i \oplus b_j$$ 的值。
对于长度为 n 的排列,您的程序不应进行超过 2n 次关于异或和的查询。请注意,打印答案不算作查询。请注意,您不能提出超过 2n 个问题。如果您提出超过 2n 个问题或至少一个不正确的问题,您的解决方案将得到“错误答案”。
如果在某个时刻你的程序读取 -1 作为答案,它应该立即退出(例如,通过调用 exit(0))。在这种情况下你会得到“错误答案”,这意味着你问了超过 2n 个问题,或者问了一个无效的问题。如果您忽略这一点,您可以获得其他结论,因为您的程序将继续从关闭的流中读取。
如果您不打印任何内容或忘记刷新输出(包括最终答案),您的解决方案将得到“超出空闲限制”。
要刷新,您可以使用(在打印换行符之后):
- C++ 中的 fflush(stdout);
- Java 中的 System.out.flush();
- Python 中的 stdout.flush() ;
- 帕斯卡刷新(输出);
- 对于其他语言,请参阅文档。
黑客攻击
对于黑客攻击,请使用以下格式:
n
p0 p1 ... pn - 1
参赛者程序将无法看到此输入。
输出
当程序准备好打印答案时,打印三行。
在第一行打印“!”。
在第二行中打印单个整数answers_cnt — 与隐藏排列(包括隐藏排列)无法区分的排列数量。
在第三行中打印 n 个整数 p0, p1, ..., pn - 1(0 ≤ pi < n,所有 pi 应该不同)——与隐藏排列无法区分的排列之一。
你的程序应该在打印答案后终止。
示例
输入 #1
3 0 0 3 2 3 2
输出 #1
? 0 0 ? 1 1 ? 1 2 ? 0 2 ? 2 1 ? 2 0 ! 1 0 1 2
输入 #2
4 2 3 2 0 2 3 2 0
输出 #2
? 0 1 ? 1 2 ? 2 3 ? 3 3 ? 3 2 ? 2 1 ? 1 0 ? 0 0 ! 2 3 1 2 0
注意
异或运算,或按位异或,是对两个整数执行的运算,其中,当且仅当两个整数中恰好有一个整数的二进制表示形式的第 i 位等于 1 时,结果的二进制表示形式的第 i 位数字等于 1。有关详细信息,请参阅此处。
在第一个示例中,p = [0, 1, 2],因此 b = [0, 1, 2],对于给定的 i、j,值 $$p_i \oplus b_j$$ 是正确的。没有其他排列可以为给定的查询提供相同的答案。
查询的答案是:
- $$p_{0} \oplus b_{0} = 0 \oplus 0 = 0$$,
- $$p_{1} \oplus b_{1} = 1 \oplus 1 = 0$$,
- $$p_{1} \oplus b_{2} = 1 \oplus 2 = 3$$,
- $$p_{0} \oplus b_{2} = 0 \oplus 2 = 2$$,
- $$p_{2} \oplus b_{1} = 2 \oplus 1 = 3$$,
- $$p_{2} \oplus b_{0} = 2 \oplus 0 = 2$$。
在第二个示例中,p = [3, 1, 2, 0] 和 b = [3, 1, 2, 0],值 $$p_i \oplus b_j$$ 与所有对 i、j 匹配。但还有一种更合适的排列 p = [0, 2, 1, 3], b = [0, 2, 1, 3] 也匹配所有 n2 个可能的查询。所有其他排列甚至与显示的查询也不匹配。