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)**
本题使用的交互库见下文公示。为避免评测出现意外情况，请不要混用多种输入输出。
:::info
```cpp
#include "testlib.h"
#include
#include
#include
using namespace std;
const int MAX_QUERIES = 300000;
const int BLOCK_SIZE = 777;
const string SECRET = "Well, contestant made it, just accept it";
class SQRTDecomposition {
private:
vector array;
vector block;
vector sorted;
int getCountLessForBlock(const vector& a, int value) {
int l = -1;
int r = a.size();
while (l < r - 1) {
int mid = (l + r) / 2;
if (a[mid] >= value) r = mid;
else l = mid;
}
return r;
}
public:
SQRTDecomposition(const vector& a) {
array = a;
int n = a.size();
sorted.resize((n + BLOCK_SIZE - 1) / BLOCK_SIZE);
block.resize(n);
for (int i = 0, b = 0; i < n; i += BLOCK_SIZE, b++) {
int to = min(n, i + BLOCK_SIZE);
for (int k = i; k < to; k++) {
block[k] = b;
}
sorted[b].assign(array.begin() + i, array.begin() + to);
sort(sorted[b].begin(), sorted[b].end());
}
}
void set(int x, int y) {
int old = array[x];
array[x] = y;
vector& curBlock = sorted[block[x]];
bool found = false;
for (int i = 0; i < curBlock.size(); i++) {
if (curBlock[i] == old) {
found = true;
curBlock[i] = y;
while (i + 1 < curBlock.size() && curBlock[i + 1] < curBlock[i]) {
swap(curBlock[i], curBlock[i + 1]);
i++;
}
while (i - 1 >= 0 && curBlock[i - 1] > curBlock[i]) {
swap(curBlock[i], curBlock[i - 1]);
i--;
}
break;
}
}
if (!found) {
quitf(_fail, "Internal error: element not found in block");
}
}
int getCountLess(int l, int r, int value) {
r--;
if (l > r) return 0;
int leftBlock = block[l];
int rightBlock = block[r];
if (leftBlock == rightBlock) {
int ret = 0;
while (l MAX_QUERIES) {
isExceedMaxquery = true;
}
int x = ouf.readInt() - 1;
int y = ouf.readInt() - 1;
if (x < 0 || x >= n) {
quitf(_wa, "x = %d, index is out of array bounds", x + 1);
}
if (y < 0 || y >= n) {
quitf(_wa, "y = %d, index is out of array bounds", y + 1);
}
if (x == y) {
quitf(_wa, "swapping element %d with itself", x + 1);
}
if (x > y) {
swap(x, y);
}
int countLess1 = tree.getCountLess(x + 1, y, p[x]);
int countLess2 = tree.getCountLess(x + 1, y, p[y]);
countInversions += countLess2 * 2 - countLess1 * 2;
swap(p[x], p[y]);
tree.set(x, p[x]);
tree.set(y, p[y]);
if (p[x] < p[y]) {
countInversions--;
} else {
countInversions++;
}
printf("%lld\n", countInversions);
fflush(stdout);
} else {
quitf(_wa, "Invalid query command: %s", s.c_str());
}
}
return 0;
}
```
:::
题目描述
彼佳（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$ |