# IOI '96 P4 - Sorting a Three-Valued Sequence

Jun 6th, 2022
625
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <vector>
3.
4. using namespace std;
5.
6. int main() {
7.     int n; cin >> n;
8.     vector<int> a(n);
9.     int f[3]{};
10.     for (int &x : a) cin >> x, ++f[x-1];
11.
12.     vector<int> pos[3][3]{}; // pos[i][j] => value i in place of value j
13.     for (int i = 0; i < n; ++i) {
14.         int j = 0;
15.         if (i >= f[0]) ++j;
16.         if (i >= f[0]+f[1]) ++j;
17.         pos[a[i]-1][j].push_back(i);
18.     }
19.
20.     vector<pair<int, int>> swaps;
21.     // Direct swaps to correct places
22.     for (int i = 0; i < 3; ++i) {
23.         for (int j = i+1; j < 3; ++j) {
24.             while (!pos[i][j].empty() && !pos[j][i].empty()) {
25.                 swaps.emplace_back(pos[i][j].back(), pos[j][i].back());
26.                 pos[i][j].pop_back(), pos[j][i].pop_back();
27.             }
28.         }
29.     }
30.     // Cyclic swaps
31.     for (int i = 1; i <= 2; ++i) { // Only one of these two iterations will do anything
32.         while (!pos[0][i].empty()) {
33.             int j = 3-i;
34.             int x = pos[0][i].back(), y = pos[i][j].back(), z = pos[j][0].back();
35.             pos[0][i].pop_back(), pos[i][j].pop_back(), pos[j][0].pop_back();
36.             swaps.emplace_back(x, z);
37.             swaps.emplace_back(x, y);
38.         }
39.     }
40.
41.     cout << swaps.size() << endl;
42.     for (auto [x, y] : swaps) cout << x+1 << ' ' << y+1 << '\n';
43.     return 0;
44. }