CF1521C Nastia and a Hidden Permutation

这是一个交互题！ Nastia 有一个长度为 $n$ 的隐藏排列 $p$，其中包含 $1$ 到 $n$ 的整数。你出于某种原因想要找出这个排列。为此，你可以给她一个整数 $t$（$1 \le t \le 2$）、两个不同的下标 $i$ 和 $j$（$1 \le i, j \le n$，$i \neq j$），以及一个整数 $x$（$1 \le x \le n - 1$）。 根据 $t$ 的不同，她会回答你： - $t = 1$：$\max{(\min{(x, p_i)}, \min{(x + 1, p_j)})}$； - $t = 2$：$\min{(\max{(x, p_i)}, \max{(x + 1, p_j)})}$。 你最多可以询问 Nastia $\lfloor \frac {3 \cdot n} { 2} \rfloor + 30$ 次。保证她不会根据你的询问改变她的排列。你能猜出这个排列吗？

输入包含若干组测试数据。首先，你会收到一个整数 $T$（$1 \le T \le 10\,000$）——表示测试用例的数量。 每组测试数据开始时，你会收到一个整数 $n$（$3 \le n \le 10^4$）——表示排列 $p$ 的长度。 保证排列在你询问前已经确定，并且单次测试中所有 $n$ 的总和不超过 $2 \cdot 10^4$。

每次询问时，输出 "? $t$ $i$ $j$ $x$"（$t = 1$ 或 $t = 2$，$1 \le i, j \le n$，$i \neq j$，$1 \le x \le n - 1$），然后读取答案。 如果我们返回 $-1$ 而不是有效答案，说明你超出了询问次数限制或询问不合法。收到 $-1$ 后应立即退出，否则你的程序会继续读取已关闭的流，可能导致任意判题结果。 当你猜出排列后，输出 "! $p_1$ $p_2$ $\ldots$ $p_n$"（不带引号）。注意，输出答案不计入 $\lfloor \frac {3 \cdot n} { 2} \rfloor + 30$ 次询问限制。 每次输出询问或答案后，别忘了输出换行并刷新输出缓冲区，否则会因“超出空闲时间限制”被判为超时。具体做法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 Hack 数据 要 Hack 其它解法，请使用如下测试格式。 第一行包含一个整数 $T$（$1 \le T \le 10\,000$）——表示测试用例数量。 每组测试数据第一行输出一个整数 $n$（$3 \le n \le 10^4$）——隐藏排列 $p$ 的长度。 第二行输出 $n$ 个用空格分隔的整数 $p_1, p_2, \ldots, p_n$（$1 \le p_i \le n$），表示排列 $p$。 注意，所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^4$。

考虑第一个测试用例。 隐藏排列为 $[3, 1, 4, 2]$。 我们输出："? 2 4 1 3"，得到 $\min{(\max{(3, p_4)}, \max{(4, p_1)})} = 3$。 我们输出："? 1 2 4 2"，得到 $\max{(\min{(2, p_2)}, \min{(3, p_4)})} = 2$。 再看第二个测试用例。 隐藏排列为 $[2, 5, 3, 4, 1]$。 我们输出："? 2 3 4 2"，得到 $\min{(\max{(2, p_3)}, \max{(3, p_4)})} = 3$。 由 ChatGPT 4.1 翻译