题目描述

题目译自 XXXII Olimpiada Informatyczna – II etap Porządki

Bajtazar 决定大干一场，整理自己的房间！然而，进展并不顺利，其中一个难题是整理书架上的 $n$ 本书。书架有 $n$ 个位置，编号 $1$ 到 $n$，每个位置放一本编号为 $1$ 到 $n$ 的书。目标是让书 $1$ 在位置 $1$，书 $2$ 在位置 $2$，依此类推。Bajtazar 能快速计算当前排列的逆序对数，即满足 $i < j$ 且 $p_i > p_j$ 的位置对 $(i, j)$，其中 $p_i$ 和 $p_j$ 是位置 $i$ 和 $j$ 上的书编号。

你的任务是帮助 Bajtazar 整理书架，最多进行 $m$ 次操作。每次操作选择两个位置（可相同），交换两处书籍，并从 Bajtazar 处获知交换后的逆序对数。最终，书架上的书需按 $1, 2, \ldots, n$ 顺序排列。

交互方式

本题为交互题，需编写程序通过操作整理 Bajtazar 的书架，最终实现排序。程序可通过提供的库或标准输入输出与评测进程交互，任选一种方式，但不可同时使用两者。选手文件提供两种交互方式的示例实现。程序不可打开任何文件，可使用标准错误输出（stderr），但需注意时间消耗。标准输出的冗余数据可能导致「Wrong Answer」评测结果。

方式 1：使用库交互

C++

程序开头需包含：

#include "porlib.h"

库提供以下函数：

• int DajN()：返回书本数量 $n$。
• int Zamiana(int a, int b)：交换位置 $a$ 和 $b$ $(1 \leq a, b \leq n)$ 上的书，返回交换后的逆序对数。若返回 $0$，表示书已排序，程序应终止，不再调用库函数。

Python

程序开头需包含：

from porlib import DajN, Zamiana

库提供以下函数：

• DajN()：返回书本数量 $n$。
• Zamiana(a: int, b: int)：交换位置 $a$ 和 $b$ $(1 \leq a, b \leq n)$ 上的书，返回交换后的逆序对数。若返回 $0$，表示书已排序，程序应终止，不再调用库函数。

库函数可任意顺序调用，DajN 可多次调用。使用无效参数调用函数，或同时使用标准输入输出，将导致「Wrong Answer」评测结果。

方式 2：标准输入输出交互

第一行从标准输入读取一个整数 $n$，表示书本数量。随后，程序需向标准输出写入两个整数 $a, b$，表示要交换的位置，空格分隔并以换行符结束；然后从标准输入读取一个整数，表示交换后的逆序对数。若读取到 $0$，表示书已排序，程序应终止，不再进行输入输出交互。

C++（标准输入输出）

包含头文件 <iostream>，输出每行需使用 std::endl。示例交互代码：

std::cin >> n;
std::cout << a << " " << b << std::endl;
std::cin >> number_of_inversions;

C++（stdio 输入输出）

包含头文件 <cstdio>，输出每行需调用 fflush(stdout)。示例交互代码：

scanf("%d", &n);
printf("%d %d\n", a, b);
fflush(stdout);
scanf("%lld", &number_of_inversions);

Python

输出每行需设置 flush=True。示例交互代码：

n = int(input())
print(f"{a} {b}", flush=True)
number_of_inversions = int(input())

样例

假设初始书排列为 $1, 3, 2, 4, 6, 5$，操作上限 $m=1000$。程序可能按以下流程执行：

附加样例

1. $n=6, m=1000$，初始排列为 $4, 2, 5, 1, 3, 6$。
2. $n=1000, m=50000$，初始排列为降序序列 $1000, 999, \ldots, 1$。
3. $n=10000, m=50000$，初始排列由两个升序段组成：前半为奇数 $1, 3, \ldots$，后半为偶数 $2, 4, \ldots$。

示例程序

「文件」中提供了 C++ 和 Python 的示例（错误）解决方案，展示两种交互方式，以及交互库和示例评测程序：

• por.cpp：基于 std::cin 和 std::cout 的交互示例。
• por.py：基于 input() 和 print() 的交互示例。
• por2.cpp：基于 porlib.h 的交互示例。
• por2.py：基于 porlib.py 的交互示例。

C++ 示例和评测程序可通过 make 编译，生成 por.e 和 por2.e。运行程序使用 run.sh 脚本，例如：

• ./run.sh "./por.e"
• ./run.sh "python3 por.py"
• ./run.sh "./por2.e"
• ./run.sh "python3 por2.py"

程序从 input.in 读取数据，格式为：

• 第一行：两个整数 $n, m$。
• 第二行：$1$ 到 $n$ 的排列，表示初始书序。

示例评测程序与评测时使用的评测程序不同，可能不验证输入或函数参数的合法性。提交的代码将在样例上使用正式评测程序。

数据范围与提示

详细子任务附加限制及分值如下表所示。