CF2190C Comparable Permutations

本题为交互题。 对于一个排列 $^{\text{∗}}$ $g = (g_1, g_2, \ldots, g_m)$，定义其反转为 $\operatorname{rev}(g) = (g_m, g_{m-1}, \ldots, g_1)$。 现在有一个长度为 $n$ 的隐藏排列 $p$。你的任务是找到长度为 $n$ 的字典序最小的 $^{\text{†}}$ 排列 $q$，满足 $q > p$ 且 $\operatorname{rev}(q) > \operatorname{rev}(p)$。 但你不需直接输出 $q$。你需要输出一个长度为 $n$ 的排列 $r$，使得对于所有 $1 \leq i \leq n$，都有 $q_i = p_{r_i}$。如果不存在满足条件的 $q$，则需要报告不存在。 为了寻找答案，你可以最多对每个测试用例询问 $3n$ 次形如 $\texttt{? } i\; j$（$1 \leq i, j \leq n$）的查询。交互器会返回 $1$，当且仅当 $p_i < p_j$，否则返回 $0$。交互器是非自适应的，也就是说，在整个交互过程中排列 $p$ 始终不变。 $^{\text{∗}}$ 长度为 $n$ 的排列是由 $1$ 到 $n$ 的 $n$ 个互不相同的整数组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（$2$ 在数组中出现了两次），$[1,3,4]$ 也不是排列（$n=3$ 但数组中有 $4$）。 $^{\text{†}}$ 一个数组 $x$ 字典序小于数组 $y$（记作 $x < y$ ），当且仅当满足以下之一： - $x$ 是 $y$ 的前缀，但 $x \ne y$； - 存在最小的下标 $i$，使得 $x_i \neq y_i$，那么如果 $x_i < y_i$ 则 $x < y$。

每个测试点包含多个测试用例。第一行包含整数 $t$（$1 \leq t \leq 1000$），表示测试用例个数。每个测试用例描述如下： 每个测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 2 \cdot 10^4$），表示隐藏排列 $p$ 的长度。 隐藏排列 $p$ 在此测试用例被随机选定且在交互过程中不变。换句话说，交互器是非自适应的。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^4$。

对于每个测试用例，首先读取一个整数 $n$。 对于每个测试用例，你最多可以进行 $3n$ 次查询。 每次查询，输出一行 $\texttt{?}\; i\; j$（$1 \le i, j \le n$）。 每次交互器返回： - $1$，如果 $p_i < p_j$； - $0$，如果 $p_i \geq p_j$； - $-1$，如果你的查询不合法或者超过了 $3n$ 次查询。 如果你对一个测试用例进行了多于 $3n$ 次查询，或进行了不合法的查询，将收到 $-1$ 的反馈。收到该反馈后，你的程序应立刻终止，并得到 **Wrong Answer** 判定。否则，你将可能获得其它任意判定。 当你确定出当前测试用例的答案后，请输出如下之一： - 如果不存在满足条件的排列 $q$，输出 $\texttt{!}\; -1$。 - 否则，输出 $\texttt{!}\; r_1\; r_2\; \ldots\; r_n$，其中 $r$ 是长度为 $n$ 的排列，并且满足 $q_i = p_{r_i}$。 注意，这一输出不计入 $3n$ 次查询限制。 随后请进入下一个测试用例，或所有用例处理结束后结束程序。 每输出一次查询后请不要忘记换行以及刷新输出缓冲区$^{\text{∗}}$，否则可能因“空闲超时”被判为超时。 在任何交互步骤，如果你读取到 $-1$ 作为数据而不是合法数据，你的程序必须立刻退出。这意味着你的程序因无效查询或其它错误收到 Wrong Answer。未能立即退出会导致你的程序在关闭的流上继续读取而得到不可预料的判定。 注意，交互器是**非自适应**的，也就是说整个交互过程中隐藏排列不会变化。 **Hack数据格式** Hack数据格式如下： 第一行一个正整数 $t$（$1 \leq t \leq 1000$），表示测试用例数。 每个测试用例的第一行一个正整数 $n$（$2 \leq n \leq 2 \cdot 10^4$），表示 $p$ 的长度。 每个测试用例的第二行 $n$ 个整数 $p_1,p_2,\ldots,p_n$（$1\leq p_i \leq n$）。 需保证所给 $p$ 是排列，且所有测试用例 $n$ 之和不超过 $2 \cdot 10^4$。 $^{\text{∗}}$ 输出刷新方法： - C++：fflush(stdout) 或 cout.flush() - Python：sys.stdout.flush() - 其它语言请查阅相关文档。

例如，交互过程如下： | **方案** | **评测系统** | **解释** | | --- | --- | --- | | | 3 | 有 $3$ 个测试用例。| | | 5 | 第一个用例中，隐藏排列为 $[5, 4, 2, 3, 1]$，长度为 $5$。对应的排列 $q = [5, 4, 3, 1, 2]$。| | ? 2 1 | 1 | 方案询问 $p_2 \lt p_1$，评测系统返回 $1$，因为 $4 < 5$。 | | ! 1 2 4 5 3 | | 方案据此得出答案并输出 $r = [1, 2, 4, 5, 3]$。例如 $q_3 = p_{r_3} = p_4 = 3$，$q_2 = p_{r_2} = p_2 = 4$。| | | 4 | 第二个用例中，隐藏排列为 $[3, 1, 2, 4]$，长度为 $4$。不存在满足条件的排列 $q$。| | ? 2 3 | 1 | 方案询问 $p_2 \lt p_3$，评测系统返回 $1$。| | ? 1 3 | 0 | 方案询问 $p_1 \lt p_3$，返回 $0$。| | ? 1 4 | 1 | 方案询问 $p_1 \lt p_4$，返回 $1$。| | ? 2 2 | 0 | 方案询问 $p_2 \lt p_2$，返回 $0$。| | ! -1 | | 方案据此得出当前排列 $p = [3, 1, 2, 4]$，确认不存在满足要求的 $q$，输出 $-1$。| | | 9 | 第三个用例，$p = [8, 1, 9, 3, 5, 4, 2, 6, 7]$，长度 $n = 9$。| | ! 1 2 3 6 7 4 5 8 9 | | 方案尝试猜答案并输出 $r = [1, 2, 3, 6, 7, 4, 5, 8, 9]$，结果正确。| 注意，样例中的空行仅用于便于阅读，真实输入输出中不会出现。 由 ChatGPT 5 翻译