P14274 [ROI 2014 Day1] Petya 与机器人

**译自 [ROI 2014](https://neerc.ifmo.ru/school/archive/2013-2014.html) Day1 T3.** ***[Петя и Робот](https://neerc.ifmo.ru/school/archive/2013-2014/ru-olymp-roi-2014-statement-day1.pdf)***

彼佳（Petya）的书架上摆放着 $n$ 本记录了他所有创意的笔记本。每本笔记本的编号是从 1 到 $n$ 的**互不相同的整数**。他有一种自己习惯的笔记本摆放顺序（不一定是 1 到 $n$ 的顺序），并且他不喜欢别人移动它们。 为了保存这个顺序并计算其“混乱程度”，彼佳买了一个特别的机器人。机器人可以记住当前笔记本的顺序，并计算其中的“混乱数”。 如果一对笔记本中，编号较小的笔记本出现在编号较大的笔记本的右边，那么这对笔记本就形成一个**混乱对**。例如，在排列 $(2,~1,~5,~3,~4)$ 中，有三对混乱对：$(2,1)$、$(5,3)$、$(5,4)$，因此混乱数为 $3$。 打扫房间后，彼佳忘记了自己习惯的笔记本顺序，现在想要将其恢复。机器人记住了这个顺序，但它**只能告诉彼佳当前顺序中的混乱数**。 彼佳还可以让机器人执行如下操作： - 交换当前排列中的任意两本笔记本的位置。 交换后，机器人会保存**新的排列**，并告知其混乱数。彼佳可以不断进行这种询问，直到觉得自己获得了足够的信息从而确定原始排列。 你的任务是编写一个程序，通过与机器人交互，恢复原始笔记本的顺序。 ### 交互格式（Interaction） 这是一个交互式问题。你的程序需要通过标准输入/输出，与评测程序（模拟机器人）进行交互。 首先，你的程序应读入两个整数： - $n$ —— 笔记本的数量； - $m$ —— 原始排列中的混乱数。 接下来，你的程序与评测程序的交互规则如下： - 若要交换两本笔记本的位置，请输出：$\tt{swap}$ $i$ $j$ 其中 $i$ 和 $j$ 是笔记本当前排列中的位置编号（$1 \le i, j \le n$, 且 $i \ne j$）。随后需读取一个整数——交换后的排列的混乱数。你的程序最多可以发出 $300 000$ 次这样的交换请求。 - 当你已经确定了原始的排列，应输出：$\tt{answer}$ $p$ 其中 $p$ 是长度为 $n$ 的一个排列，表示最终恢复的顺序（数值为 1 到 $n$，互不重复）。输出后程序应立即结束。 所有输出行都必须以换行符结束，并**刷新输出缓冲区**，例如使用： - Pascal：`flush(output)` - C/C++：`fflush(stdout)` 或 `cout.flush()`

无

无

### 数据范围 本题共四个子任务。子任务 $1$ 需要全部通过才能得分；子任务 $2\sim 4$ 各自独立计分。 | 子任务 | 分值 | 限制 | |:--:|:--:|:--:| | 1 | 30 | $1 \le n \le 100$ | | 2 | 20 | $1 \le n \le 8000$ | | 3 | 30 | $1 \le n \le 60\,000$ | | 4 | 20 | $1 \le n \le 100\,000$ |