[ROI 2014 Day1] Petya 与机器人

ID: 16063

远端评测题

3000ms

256MiB

难度: 5

上传者:

标签>

2014

线段树

交互题

Special Judge

ROI（俄罗斯）

题目背景

译自 ROI 2014 Day1 T3. Петя и Робот

彼佳（Petya）的书架上摆放着 $n$ 本记录了他所有创意的笔记本。每本笔记本的编号是从 1 到 $n$ 的互不相同的整数。他有一种自己习惯的笔记本摆放顺序（不一定是 1 到 $n$ 的顺序），并且他不喜欢别人移动它们。

为了保存这个顺序并计算其“混乱程度”，彼佳买了一个特别的机器人。机器人可以记住当前笔记本的顺序，并计算其中的“混乱数”。

如果一对笔记本中，编号较小的笔记本出现在编号较大的笔记本的右边，那么这对笔记本就形成一个混乱对。例如，在排列 $(2,~1,~5,~3,~4)$ 中，有三对混乱对： $(2,1)$ 、 $(5,3)$ 、 $(5,4)$ ，因此混乱数为 $3$ 。

打扫房间后，彼佳忘记了自己习惯的笔记本顺序，现在想要将其恢复。机器人记住了这个顺序，但它只能告诉彼佳当前顺序中的混乱数。

彼佳还可以让机器人执行如下操作：

交换后，机器人会保存新的排列，并告知其混乱数。彼佳可以不断进行这种询问，直到觉得自己获得了足够的信息从而确定原始排列。

你的任务是编写一个程序，通过与机器人交互，恢复原始笔记本的顺序。

这是一个交互式问题。你的程序需要通过标准输入/输出，与评测程序（模拟机器人）进行交互。

首先，你的程序应读入两个整数：

接下来，你的程序与评测程序的交互规则如下：

若要交换两本笔记本的位置，请输出： $\tt{swap}$ $i$ $j$

其中 $i$ 和 $j$ 是笔记本当前排列中的位置编号（ $1 \le i, j \le n$ , 且 $i \ne j$ ）。随后需读取一个整数——交换后的排列的混乱数。你的程序最多可以发出 $300 000$ 次这样的交换请求。
当你已经确定了原始的排列，应输出： $\tt{answer}$ $p$

其中 $p$ 是长度为 $n$ 的一个排列，表示最终恢复的顺序（数值为 1 到 $n$ ，互不重复）。输出后程序应立即结束。

所有输出行都必须以换行符结束，并刷新输出缓冲区，例如使用：

3 2
1
0

swap 1 3
swap 3 2
answer 2 3 1

本题共四个子任务。子任务 $1$ 需要全部通过才能得分；子任务 $2\sim 4$ 各自独立计分。