← 返回题目列表

Codeforces · 2173/E

E. 白的镜子决斗

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

这个世界上没有运气这回事。胜利者在比赛开始之前就已经决定了。
— 没有游戏就没有生活

这是一个交互问题。

有一天,Sora和Shiro再次感到无聊,所以他们决定用游戏来解决这个问题。

一开始,Sora给Shiro一个排列$$$^{\text{*}}$$$ $$$p_1,p_2,\ldots,p_n$$$,长度为$$$n$$$。在每个操作中,Shiro 可以选择两个不同的索引 $$$x$$$ 和 $$$y$$$ ($$$1\le x\ne y\le n$$$)。然后索拉抛了一枚公平的硬币:

  • Sora 以 $$$0.5$$$ 的概率交换 $$$p_x$$$ 和 $$$p_y$$$;
  • Sora 以 $$$0.5$$$ 的概率交换 $$$p_{n-x+1}$$$ 和 $$$p_{n-y+1}$$$。

操作完成后,Sora 回复实际交换的一对索引,以便 Shiro 可以相应地更新她的本地排列。

Shiro 的目标是通过最多使用 $$$\lfloor 2.5n+800\rfloor$$$ 操作对排列 $$$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 100$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 4000$$$) — $$$p$$$ 的长度。

第二行包含 $$$n$$$ 整数 $$$p_1,p_2,\ldots,p_n$$$ — $$$p$$$ 的元素。

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

这个问题保证有 $$$50$$$ 测试。

互动

对于每个测试用例,您最多可以使用 $$$\lfloor 2.5n+800\rfloor$$$ 移动来按升序对排列 $$$p$$$ 进行排序。

要进行移动,您应该按以下格式打印新行:

  • $$$\mathtt{?}\; x\; y$$$ ($$$1 \le x \ne y \le n$$$) — Shiro 在这一步中选择的两个索引。

作为对此举的回应,您将收到两个整数 $$$u$$$ 和 $$$v$$$ — Sora 交换的实际索引对。保证 $$$(u, v)$$$ 是从 $$$(x, y)$$$ 和 $$$(n-x+1, n-y+1)$$$ 中等概率随机选择的。

要报告排列已按升序排序,您应该打印一个包含单个字符 $$$\mathtt{!}$$$ 的新行。这确实 不 算作 $$$\lfloor 2.5n+800\rfloor$$$ 移动之一。

之后,继续进行下一个测试用例,或者如果是最后一个测试用例则终止程序。

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

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

在此问题中,黑客被禁用。

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

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

示例

输入
复制

2
5
5 1 3 4 2

1 5

2 1

2
1 2

输出
复制



? 1 5

? 4 5

!


!

注意

在第一个测试用例中,$$$n=5$$$,初始排列为$$$[5,1,3,4,2]$$$。

  • 我们打印 ? 1 5。法官回复 1 5,表示位置 $$$1$$$ 和 $$$5$$$ 被交换(无镜像)。该数组变为$$$[2,1,3,4,5]$$$。
  • 我们打印 ? 4 5。法官回复 2 1,它是 $$${4,5}$$$ 的镜像,因为 $$$n=5$$$ 我们有 $$$n-4+1=2$$$ 和 $$$n-5+1=1$$$。因此我们必须交换位置 $$$2$$$ 和 $$$1$$$。该数组变为$$$[1,2,3,4,5]$$$。
  • 排列现已排序,因此我们打印 !。答案行不计入操作限制。

在第二个测试用例中,给定的排列已经在增加,所以我们只需要输出 !.