CF870D Something with XOR Queries

这是一个交互式问题。 评测机隐藏了一个长度为 $n$ 的排列 $p$，排列元素为 $0$ 到 $n-1$ 的整数。你只知道排列的长度 $n$。请注意，排列中的所有整数都是互不相同的。 设 $b$ 是 $p$ 的逆排列，即对于所有 $i$，有 $p_{b_i}=i$。你唯一可以做的操作是询问 $p_i$ 与 $b_j$ 的异或值（xor），具体方式为给出两个下标 $i$ 和 $j$（二者可以相同也可以不同）。对于下标 $i$ 和 $j$ 的一次询问，你会得到 $p_i \oplus b_j$ 的结果，这里 $\oplus$ 表示异或运算。 请注意，即使你进行所有 $n^{2}$ 次可能的询问，有些排列依旧无法和隐藏排列区分开。你需要计算出所有与隐藏排列无法区分的排列个数，并输出其中一个排列，并且总询问次数不得超过 $2n$。 隐藏排列与你的询问无关。

第一行包含一个整数 $n$（$1 \leq n \leq 5000$）——隐藏排列的长度。你首先要读取该整数。

当你准备好输出答案时，请依次输出三行： 第一行输出一个感叹号 "!"。 第二行输出单个整数 $answers\_cnt$，表示所有与隐藏排列无法区分的排列个数（包括隐藏排列本身）。 第三行输出 $n$ 个整数 $p_0, p_1, ..., p_{n-1}$（$0 \leq p_i < n$，并且所有 $p_i$ 互不相同），即输出一个与隐藏排列无法区分的排列。 输出答案后，程序应终止。 # 交互方式 你可以通过输出 "? i j"（$i, j$ 均为 $0$ 到 $n-1$ 之间的整数）来询问 $p_i \oplus b_j$ 的结果。每次询问后，记得换行并刷新输出缓冲区。 针对一次询问，你会读入一个整数，表示 $p_i \oplus b_j$ 的结果。 对于一个长度为 $n$ 的排列，你总共最多可以进行 $2n$ 次询问。请注意，输出答案不计入询问次数。超过 $2n$ 次询问或有非法询问会导致评测失败。 如果在任何时刻你读入 $-1$ 作为答案，应该立即退出（比如调用 exit(0)）。此时会被判为 "Wrong answer"，表明你询问次数已超过 $2n$ 或询问了非法下标。如果忽略此行为，程序继续读取也会被判定为其它错误。 如果程序没有输出或未正确刷新输出缓冲区（包括最终答案输出），会被判定为 "Idleness Limit Exceeded"。 C++使用 fflush(stdout) 刷新输出； Java使用 System.out.flush(); Python使用 stdout.flush(); Pascal使用 flush(output)； 其它语言请自行查阅文档。 # 样例输入格式（hack 格式，仅评测机可见） $n$ $p_0\ p_1\ ...\ p_{n-1}$ 选手的程序是看不到这些输入的。

异或运算是两个整数的按位异或，其第 $i$ 位二进制结果为 $1$ 当且仅当两个数在该位上只有一个为 $1$。更多信息参考[这里](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。 在第一个样例中，$p=[0,1,2]$，$b=[0,1,2]$。对于给定的 $i, j$，所有 $p_i \oplus b_j$ 的查询值都正确。没有其它排列能匹配给定所有查询。 各个查询的答案分别如下： - $p_0 \oplus b_0$ - $p_1 \oplus b_0$ - $p_2 \oplus b_0$ - $p_0 \oplus b_1$ - $p_1 \oplus b_1$ - $p_2 \oplus b_1$ 在第二个样例中，$p=[3,1,2,0]$，$b=[3,1,2,0]$。对于所有 $i,j$，$p_i \oplus b_j$ 的值都匹配。但还有另外一个合法排列 $p=[0,2,1,3]$，$b=[0,2,1,3]$ 可以使得所有 $n^{2}$ 次查询答案全部相同。其它排列无法匹配所有已知查询。 由 ChatGPT 5 翻译