CF1815B Sum Graph

这是一个交互题。 有一个隐藏的排列 $p_1, p_2, \dots, p_n$。 考虑一个只有 $n$ 个点、没有边的无向图。你可以进行两种类型的操作： 1. 指定一个整数 $x$，满足 $2 \le x \le 2n$。对于所有满足 $1 \le i \le n$ 且 $1 \le x-i \le n$ 的整数 $i$，在节点 $i$ 和节点 $x-i$ 之间添加一条边。 2. 查询节点 $p_i$ 和节点 $p_j$ 之间最短路径的边数。你将获得这两个节点之间最短路径的边数作为答案，如果不存在这样的路径，则返回 $-1$。 注意，你可以以任意顺序进行上述两种类型的操作。 在 $2n$ 次操作（包括类型 $1$ 和类型 $2$）内，猜测出两个可能的排列，其中至少有一个是 $p_1, p_2, \dots, p_n$。如果你猜测的两个排列中至少有一个与隐藏排列完全一致，则本测试点通过。你可以两次猜测同一个排列。 长度为 $n$ 的排列是一个由 $n$ 个 $1$ 到 $n$ 的不同整数组成的数组，顺序任意。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（$2$ 出现了两次），$[1,3,4]$ 也不是排列（$n=3$ 但出现了 $4$）。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 100$）——测试数据组数。 每组测试数据的第一行包含一个整数 $n$（$2 \le n \le 10^3$）——排列的长度。 保证所有测试数据中 $n$ 的总和不超过 $10^3$。

每组测试数据的交互从读取整数 $n$ 开始。 然后，最多可以进行 $2n$ 次操作： - 如果你想进行类型 $1$ 的操作，输出 "+ x"。$x$ 必须是 $2$ 到 $2n$ 之间的整数（包含端点）。之后读取 $1$ 或 $-2$。如果读取到 $1$，说明操作有效；否则说明操作无效或已超出操作次数限制，你的程序必须立即终止，否则会被判为 Wrong Answer。 - 如果你想进行类型 $2$ 的操作，输出 "? i j"。$i$ 和 $j$ 必须是 $1$ 到 $n$ 之间的整数（包含端点）。之后读取一个整数 $r$（$-1 \le r \le n$）——这是你查询的答案。如果你收到 $-2$，说明你的操作无效或已超出操作次数限制，你的程序必须立即终止，否则会被判为 Wrong Answer。 在任何时刻，如果你想猜测两个排列，输出 "! $p_{1,1}$ $p_{1,2}$ $\dots$ $p_{1,n}$ $p_{2,1}$ $p_{2,2}$ $\dots$ $p_{2,n}$"。注意，两个排列应在同一行输出，不需要用感叹号分隔。之后读取 $1$ 或 $-2$。如果读取到 $1$，说明你的答案正确，否则说明答案错误，你的程序必须立即终止，否则会被判为 Wrong Answer。之后进入下一组测试数据，或如果没有更多测试数据则终止程序。注意，报告答案不计入操作次数。 注意，即使你输出了正确的排列，第二个排列也必须是一个合法的排列，而不能是任意数组。 在任何时刻，如果你在读取到 $-2$ 后继续交互，你可能会得到任意判题结果，因为你的程序会继续从已关闭的流中读取数据。 每次输出操作或答案后，不要忘记输出换行并刷新输出流。否则会被判为 Idleness limit exceeded。具体做法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 判题器是非自适应的。这意味着所有排列在交互开始前就已确定。 Hack 格式 要进行 hack，请使用如下格式。 第一行包含一个整数 $t$（$1 \le t \le 100$）——测试数据组数。 每组测试数据的第一行包含一个整数 $n$（$2 \le n \le 10^3$）——排列的长度。 每组测试数据的第二行包含 $n$ 个不同的整数 $p_1, p_2, \ldots, p_n$（$1 \le p_i \le n$）——隐藏排列。 所有测试数据中 $n$ 的总和不超过 $10^3$。

在第一个测试点中，$n=6$，隐藏排列 $p = [1,4,2,5,3,6]$。 首先，分别对 $x=12, 2, 3$ 进行类型 $1$ 的操作。这样总共在图中添加了四条边： - 一条连接节点 $6$ 和节点 $6$ 的边。 - 一条连接节点 $1$ 和节点 $1$ 的边。 - 一条连接节点 $1$ 和节点 $2$ 的边。 - 一条连接节点 $2$ 和节点 $1$ 的边。 由于这些操作都是有效的，判题器每次都返回 $1$。 然后，查询节点 $p_1 = 1$ 和 $p_3 = 2$ 之间最短路径的边数，答案为 $1$。 接着，对 $x=5$ 进行类型 $1$ 的操作。这样又添加了四条边： - 一条连接节点 $1$ 和节点 $4$ 的边。 - 一条连接节点 $2$ 和节点 $3$ 的边。 - 一条连接节点 $3$ 和节点 $2$ 的边。 - 一条连接节点 $4$ 和节点 $1$ 的边。 由于该操作有效，判题器返回 $1$。 然后，查询节点 $p_1 = 1$ 和 $p_5 = 3$ 之间最短路径的边数，答案为 $2$。 再查询节点 $p_4 = 5$ 和 $p_5 = 3$ 之间最短路径的边数。由于不存在这样的路径，判题器返回 $-1$。 之后，经过一些神奇的推理，确定了两个可能的排列：第一个排列为 $[1,4,2,5,3,6]$，第二个排列为 $[1,2,3,4,5,6]$。由于第一个排列等于隐藏排列，本测试点通过。总共使用了 $7$ 次操作，未超过 $2 \cdot 6 = 12$ 次操作的限制。 由于答案正确，判题器返回 $1$。 在第二个测试点中，$n=2$，隐藏排列为 $p = [2,1]$。 由于只有 $2! = 2$ 种可能的排列，不需要进行任何操作。只需直接输出两个排列 $[1,2]$ 和 $[2,1]$ 即可。总共使用了 $0$ 次操作，未超过 $2 \cdot 2 = 4$ 次操作的限制。 由于答案正确，判题器返回 $1$。 由 ChatGPT 4.1 翻译