← 返回题目列表

Codeforces · 2190/C

C. 类似的排列

中文机器翻译题面 查看原题

这是一个交互问题。

对于排列$$$^{\text{*}}$$$ $$$g = (g_1, g_2, \ldots, g_m)$$$,将其逆定义为 $$$\operatorname{rev}(g) = (g_m, g_{m-1}, \ldots, g_1)$$$。

存在一个大小为 $$$n$$$ 的隐藏排列 $$$p$$$。你的任务是找到字典顺序最小的$$$^{\text{†}}$$$排列$$$q$$$,大小为$$$n$$$,使得$$$q \gt p$$$和$$$\operatorname{rev}(q) \gt \operatorname{rev}(p)$$$。

但是,您不需要输出 $$$q$$$ 本身。相反,您必须输出大小为 $$$n$$$ 的排列 $$$r$$$,使得对于所有 $$$1 \le i \le n$$$,$$$q_i = p_{r_i}$$$。如果不存在这样的$$$q$$$,则报告该情况。

要找到答案,您最多可以提出 $$$3n$$$ 形式的查询 $$$\texttt{? } 我 \; j$$$ ($$$1 \le i, j \le n$$$)。如果 $$$p_i \lt p_j$$$ 则交互器响应 $$$1$$$,否则响应 $$$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 \lt y$$$)当且仅当以下条件之一成立:

  • $$$x$$$ 是 $$$y$$$ 的前缀,但是 $$$x \ne y$$$;或
  • 设 $$$i$$$ 为 $$$x_i \neq y_i$$$ (如果存在)的第一个位置,然后是 $$$x_i \lt y_i$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^4$$$) — 隐藏排列 $$$p$$$ 的大小。

隐藏排列 $$$p$$$ 对于测试用例来说是固定的,并且在交互过程中不会改变。换句话说,交互者是 不自适应.

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^4$$$。

互动

对于每个测试用例,首先读取单个整数 $$$n$$$。

在每个测试用例中您最多可以提出 $$$3n$$$ 查询。

要提出查询,请以 $$$\texttt{?} \; 格式打印一行我 \; j$$$ ($$$1 \le i, j \le n$$$)。

作为对查询的响应,您将得到:

  • $$$1$$$ 如果 $$$p_i \lt p_j$$$;
  • $$$0$$$ 如果 $$$p_i \ge p_j$$$;
  • $$$-1$$$ 如果您进行了无效查询或超出了 $$$3n$$$ 查询限制。

如果您的程序对一个测试用例进行了超过 $$$3n$$$ 查询,或者进行了无效查询,则对该查询的响应将为 "-1"。收到这样的响应后,你的程序应该立即终止以接收判决 错误答案。否则,它可能会收到任何其他判决。

当您确定当前测试用例的答案时,打印以下内容之一:

  • 如果不存在有效排列 $$$q$$$,则打印 $$$\texttt{!} \; -1$$$。
  • 否则,打印 $$$\texttt{!} \; r_1 \; r_2 \; \l点\; r_n$$$,其中 $$$r$$$ 是大小 $$$n$$$ 和 $$$q_i = p_{r_i}$$$ 的排列。

请注意,此输出不计入 $$$3n$$$ 的查询限制。

之后,继续下一个测试用例,或者如果没有更多的测试用例,则终止程序。

打印每个查询后,不要忘记输出行尾并刷新$$$^{\text{*}}$$$ 输出。否则,你会得到 超出空闲限制 判决。

如果在任何交互步骤中您读取 $$$-1$$$ 而不是有效数据,您的解决方案必须立即退出。这意味着您的解决方案将收到 错误答案 由于无效查询或任何其他错误。未能退出可能会导致任意判决,因为您的解决方案将继续从关闭的流中读取。

请注意,交互器是 不自适应,这意味着隐藏排列在整个交互过程中保持不变。

黑客

要破解,请使用以下格式。

第一行应包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。

每个测试用例的第一行应包含一个正整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^4$$$) — $$$p$$$ 的大小。

每个测试用例的第二行应包含 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$)。

您必须保证给定的 $$$p$$$ 是一个排列,并且所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^4$$$。

$$$^{\text{*}}$$$要刷新,请使用:

  • fflush(标准输出) or cout.flush() 在 C++ 中; Java 中的
  • sys.stdout.flush() 在 Python 中;
  • 请参阅其他语言的文档。

示例

输入
复制

3
5

1

4

1

0

1

0

9

输出
复制


? 2 1

! 1 2 4 5 3

? 2 3

? 1 3

? 1 4

? 2 2

! -1

! 1 2 3 6 7 4 5 8 9

注意

在该示例中,交互进行如下。

解决方案评审团说明
3有 $$$3$$$ 测试用例。
5在第一个测试用例中,隐藏排列为 $$$[5, 4, 2, 3, 1]$$$,长度为 $$$5$$$。对应的排列 $$$q = [5, 4, 3, 1, 2]$$$
? 2 11解决方案询问是否 $$$p_2 \lt p_1$$$,陪审团回答 $$$1$$$,如 $$$4 \lt 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 31解决方案询问是否 $$$p_2 \lt p_3$$$,陪审团回答 $$$1$$$。
? 1 30解决方案询问是否 $$$p_1 \lt p_3$$$,陪审团回答 $$$0$$$。
? 1 41解决方案询问是否 $$$p_1 \lt p_4$$$,陪审团回答 $$$1$$$。
? 2 20解决方案询问是否 $$$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]$$$,结果是正确的。

请注意,示例输入和输出中的空行是为了清楚起见,在实际交互中不会出现。