传送门：洛谷 CF2121D 1709 | Codeforces D. 1709

更佳的阅读体验：CF2121D 题解

简要题意：给定两个长度为 $n$ 的数组 $a$ 和 $b$，其中 $1$ 到 $2 \times n$ 的每个整数恰好出现在一个数组中，通过交换相邻元素或同位置的 $a_i$ 和 $b_i$，使 $a$ 和 $b$ 都变为递增，且每个位置 $i$ 都满足 $a_i < b_i$，操作次数不超过 $1709$ 次。输出操作总数和所有操作。

本题的关键点在于，我们需要想到当 $a$ 和 $b$ 都是递增数组时，对于任意位置 $i$，交换 $a_i$ 和 $b_i$ 后，两个数组仍然递增。

基于此，我们可以想到一个朴素的方法：先分别给两个数组排序，接下来遍历从 $1$ 到 $n$ 的每个位置 $i$，如果有 $a_i > b_i$ 就交换 $a_i$ 和 $b_i$。至于排序，我们可以很自然地想到一种基于交换的排序方式——冒泡排序。

上述方法的操作次数是 $O(n^2)$ 的，因为 $n \le 40$，可以通过本题。

#include <iostream>
#include <vector>
using namespace std;

const int N = 50;
int t, n, a[N], b[N];
bool flag;
vector<pair<int, int> > ans;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    for (cin >> t; t; --t) {
        ans.clear();
        cin >> n;
        for (int i = 1; i <= n; ++i) cin >> a[i];
        for (int i = 1; i <= n; ++i) cin >> b[i];
        flag = true;
        while (flag) {
            flag = false;
            for (int i = 1; i < n; ++i) if (a[i] > a[i + 1]) {
                flag = true;
                swap(a[i], a[i + 1]);
                ans.push_back({1, i});
            }
        } flag = true;
        while (flag) {
            flag = false;
            for (int i = 1; i < n; ++i) if (b[i] > b[i + 1]) {
                flag = true;
                swap(b[i], b[i + 1]);
                ans.push_back({2, i});
            }
        } for (int i = 1; i <= n; ++i) if (a[i] > b[i])
            swap(a[i], b[i]), ans.push_back({3, i});
        cout << ans.size() << '\n';
        for (auto p : ans) cout << p.first << ' ' << p.second << '\n';
    } return 0;
}