Advertisement
erek1e

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!
C++ 1.33 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement