这是问题的困难版本。版本之间的区别在于,在此版本中,您最多可以进行 $$$10\cdot n$$$ 查询。只有解决了该问题的所有版本,您才能破解。
阿里非常喜欢巴哈明的礼物(来自问题 E),以至于他非法从加兹温前往利物浦,让足球运动员在礼物上签名。现在国际刑警组织正在寻找他,但他们提出了一项协议:解决问题,他就可以留在利物浦。但由于他现在在体育场,他无法解决这个问题 - 所以他要求你这样做。
这是一个交互问题。
有一个隐藏的排列$$$^{\text{*}}$$$ $$$p$$$,长度为$$$n\ge 4$$$,其中$$$p_i \neq i$$$ 对于每个$$$1 \leq i \leq n$$$。
最初,你应该给陪审团一个正整数 $$$k\le n$$$,这将是 常数 通过以后的查询。然后您需要使用一些查询找到排列 $$$p$$$。
在每个查询中,您向陪审团提供排列 $$$q_1, q_2, \ldots, q_n$$$。作为响应,您将收到满足以下所有条件的对 $$$(i, j)$$$ 的数量:
- $$$i \lt 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$$$ 查询,您的程序应立即终止以接收判决 错误答案。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。
打印每个查询后,不要忘记输出行尾并刷新$$$^{\text{*}}$$$ 输出。否则,你会得到 超出空闲限制 判决。
如果在任何交互步骤中您读取 $$$-1$$$ 而不是有效数据,您的解决方案必须立即退出。这意味着您的解决方案将收到 错误答案 由于无效查询或任何其他错误。未能退出可能会导致任意判决,因为您的解决方案将继续从关闭的流中读取。
黑客
要执行黑客攻击,请使用以下格式:
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 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$$$-s 都是不同的) — 排列 $$$p$$$。
保证所有测试用例的$$$n^2$$$总和不超过$$$10^4$$$。
$$$^{\text{*}}$$$要刷新,请使用:
- fflush(标准输出) or cout.flush() 在 C++ 中;
- sys.stdout.flush() 在 Python 中;
- 请参阅其他语言的文档。
示例
输入复制
2 4 1 5 1 2
输出复制
1 ? 1 2 3 4 ! 3 1 4 2 3 ? 1 2 5 4 3 ? 2 1 4 3 5 ! 3 1 2 5 4
注意
在第一个测试用例中,$$$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)$$$ 满足条件。