IOI '96 P4 - Sorting a Three-Valued Sequence

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n; cin >> n;
    vector<int> a(n);
    int f[3]{};
    for (int &x : a) cin >> x, ++f[x-1];

    vector<int> pos[3][3]{}; // pos[i][j] => value i in place of value j
    for (int i = 0; i < n; ++i) {
        int j = 0;
        if (i >= f[0]) ++j;
        if (i >= f[0]+f[1]) ++j;
        pos[a[i]-1][j].push_back(i);
    }

    vector<pair<int, int>> swaps;
    // Direct swaps to correct places
    for (int i = 0; i < 3; ++i) {
        for (int j = i+1; j < 3; ++j) {
            while (!pos[i][j].empty() && !pos[j][i].empty()) {
                swaps.emplace_back(pos[i][j].back(), pos[j][i].back());
                pos[i][j].pop_back(), pos[j][i].pop_back();
            }
        }
    }
    // Cyclic swaps
    for (int i = 1; i <= 2; ++i) { // Only one of these two iterations will do anything
        while (!pos[0][i].empty()) {
            int j = 3-i;
            int x = pos[0][i].back(), y = pos[i][j].back(), z = pos[j][0].back();
            pos[0][i].pop_back(), pos[i][j].pop_back(), pos[j][0].pop_back();
            swaps.emplace_back(x, z);
            swaps.emplace_back(x, y);
        }
    }

    cout << swaps.size() << endl;
    for (auto [x, y] : swaps) cout << x+1 << ' ' << y+1 << '\n';
    return 0;
}