CF2127G2 Inter Active (Hard Version)

**这是该问题的困难版本。不同之处在于，在本版本中，你最多可以进行 $10\cdot n$ 次查询。只有在你解决了所有版本的问题后，才可以进行 Hack。** Ali 非常喜欢 Bahamin 的礼物（见 E 题），以至于他非法从 Qazvin 前往利物浦，想让足球运动员为礼物签名。现在国际刑警正在追捕他，但他们提出了一个交易：只要他解决一个问题，就可以留在利物浦。但由于他现在正在体育场，无法自己解决，于是他请求你帮忙。 这是一个交互题。 有一个长度为 $n\ge 4$ 的隐藏排列 $p$，其中对于每个 $1 \leq i \leq n$，都有 $p_i \neq i$。 一开始，你需要给评测机输出一个正整数 $k$，满足 $1 \leq k \leq n$，且在之后的所有查询中 $k$ 都保持不变。然后你需要通过若干次查询找出排列 $p$。 每次查询时，你需要给评测机一个排列 $q_1, q_2, \ldots, q_n$。评测机会返回满足以下所有条件的有序对 $(i, j)$ 的数量： - $i < j$； - $p_{q_i} = q_j$； - $i \neq k$（$k$ 是你一开始给出的常数）。 你会得到 $n$，需要在最多 $10\cdot n$ 次查询内找出排列 $p$。 $^{\text{∗}}$长度为 $n$ 的排列是一个包含 $1$ 到 $n$ 的 $n$ 个互不相同整数的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是（$2$ 出现了两次），$[1,3,4]$ 也不是（$n=3$ 但有 $4$）。

每个测试点包含多组测试数据。第一行包含测试数据组数 $t$（$1 \le t \le 500$）。每组测试数据描述如下。 每组测试数据的唯一一行包含一个整数 $n$（$4 \leq n \leq 100$），表示排列 $p$ 的长度。 保证所有测试数据中 $n^2$ 的和不超过 $10^4$。

**交互说明** 每组测试数据的交互从读取整数 $n$ 开始。 然后你需要输出整数 $k$（$1 \leq k \leq n$）。这一步不计入查询次数。 之后你可以进行最多 $10\cdot n$ 次查询。 每次查询，输出一行，格式如下： - $\texttt{?}\,q_1\,q_2\,\ldots\,q_n$ 评测机会返回该查询的答案。 当你确定排列 $p$ 后，输出一行，格式如下： - $\texttt{!}\,p_1\,p_2\,\ldots\,p_n$ 这一步也不计入查询次数。 之后继续处理下一组测试数据，或在最后一组数据后终止程序。 交互器是**非自适应**的，即排列在你输出 $k$ 之前就已经确定。 如果你的程序进行了超过 $10\cdot n$ 次查询，应立即终止以获得 Wrong answer 判定。否则，程序继续从已关闭的流中读取数据可能会导致任意判定。 每次输出查询后，别忘了输出换行并刷新输出流。否则会因超时被判为 Idleness limit exceeded。 如果在任何交互步骤中读取到 $-1$ 而不是有效数据，你的程序必须立即退出。这意味着你的程序因无效查询或其他错误而被判为 Wrong answer。如果未能退出，程序继续从已关闭的流中读取数据可能会导致任意判定。 **Hack 格式** Hack 时使用如下格式： 每个测试点包含多组测试数据。第一行包含测试数据组数 $t$（$1 \le t \leq 500$）。每组测试数据描述如下。 每组测试数据的第一行包含一个整数 $n$（$4 \leq n \leq 100$），表示排列 $p$ 的长度。 第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$1 \le p_i \le n$，$p_i\ne i$，所有 $p_i$ 互不相同），表示排列 $p$。 保证所有测试数据中 $n^2$ 的和不超过 $10^4$。 $^{\text{∗}}$刷新输出流的方法： - C++：fflush(stdout) 或 cout.flush() - Python：sys.stdout.flush() - 其它语言请查阅相关文档。

**说明** 在第一个测试点中，$p = [3, 1, 4, 2]$。解答选择了 $k=1$，然后查询排列 $q = [1, 2, 3, 4]$。只有 $(3,4)$ 满足条件。 在第二个测试点中，$p = [3, 1, 2, 5, 4]$。解答选择了 $k=3$。 - 查询排列 $q = [1, 2, 5, 4, 3]$，只有 $(1, 5)$ 满足条件。 - 查询排列 $q = [2, 1, 4, 3, 5]$，$(1, 2)$ 和 $(2, 4)$ 满足条件。 由 ChatGPT 4.1 翻译