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 翻译