Vaihdot

#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> v(n), pos(n);
        for (int i = 0; i < n; ++i) {
            cin >> v[i];
            v[i]--;
            pos[v[i]] = i;
        }
        if (n <= 4) {
            map<vector<int>, int> dist;
            map<vector<int>, pair<int, int>> swp;
            vector<vector<int>> q;
            q.push_back(v);
            dist[v] = 0;
            for (int qi = 0; qi < int(q.size()); ++qi) {
                for (int i = 0; i < n; ++i) {
                    for (int j = i + 2; j < n; ++j) {
                        auto a = q[qi];
                        swap(a[i], a[j]);
                        if (!dist.count(a)) {
                            dist[a] = dist[q[qi]] + 1;
                            q.push_back(a);
                            swp[a] = {i, j};
                        }
                    }
                }
            }
            sort(v.begin(), v.end());
            if (!dist.count(v))
                cout << -1 << '\n';
            else {
                cout << dist[v] << '\n';
                vector<pair<int, int>> swaps;
                while (swp.count(v)) {
                    auto [i, j] = swp[v];
                    swap(v[i], v[j]);
                    swaps.emplace_back(i, j);
                }
                reverse(swaps.begin(), swaps.end());
                for (auto& [l, r] : swaps)
                    cout << l+1 << ' ' << r+1 << '\n';
            }
            continue;
        }
        vector<pair<int, int>> swaps;
        bool ok = true;
        auto do_swap = [&](int a, int b) {
            swap(v[a], v[b]);
            swap(pos[v[a]], pos[v[b]]);
            swaps.emplace_back(a, b);
        };
        for (int i = 0; i < n; ++i) {
            if (pos[i] == i)
                continue;
            if (abs(pos[i] - i) > 1) {
                do_swap(pos[i], i);
            } else {
                bool f = false;
                for (int j = 0; j < n; ++j) {
                    if (abs(i - j) > 1 && abs(pos[i] - j) > 1) {
                        f = true;
                        do_swap(pos[i], j);
                        do_swap(i, j);
                        do_swap(pos[i], j);
                        break;
                    }
                }
                if (!f)
                    ok = false;
            }
        }
        if (!ok)
            cout << -1 << '\n';
        else {
            cout << swaps.size() << '\n';
            for (auto& [l, r] : swaps)
                cout << l+1 << ' ' << r+1 << '\n';
        }
    }
}

Test 1

Group: 1, 2

Verdict: WRONG ANSWER

Test 2

Group: 2

Verdict: WRONG ANSWER