Advertisement
erek1e

IOI '15 P5 - Sorting (Standard I/O)

Jun 16th, 2022
723
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.24 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> p(n);
  9.     for (int &x : p) cin >> x;
  10.     int m; cin >> m;
  11.     vector<int> x(m), y(m);
  12.     for (int i = 0; i < m; ++i) cin >> x[i] >> y[i];
  13.  
  14.     auto perform = [&p, &x, &y](int k) {
  15.         vector<int> v = p;
  16.         for (int i = 0; i < k; ++i) swap(v[x[i]], v[y[i]]);
  17.         return v;
  18.     };
  19.  
  20.     auto minMoves = [&n](const vector<int> &v) {
  21.         vector<bool> seen(n);
  22.         int cycles = 0;
  23.         for (int i = 0; i < n; ++i) {
  24.             if (!seen[i]) {
  25.                 ++cycles;
  26.                 int j = i;
  27.                 do {
  28.                     seen[j] = true;
  29.                     j = v[j];
  30.                 } while (j != i);
  31.             }
  32.         }
  33.         return n-cycles;
  34.     };
  35.  
  36.     int left = -1, right = m+1;
  37.     while (left+1 < right) {
  38.         int k = (left + right) / 2;
  39.         vector<int> v = perform(k);
  40.         if (minMoves(v) <= k) right = k;
  41.         else left = k;
  42.     }
  43.     cout << right << endl;
  44.  
  45.     auto getMoves = [&n](const vector<int>& v) {
  46.         vector<bool> seen(n);
  47.         vector<pair<int, int>> moves; // by value (not index)
  48.         for (int i = 0; i < n; ++i) {
  49.             if (!seen[i]) {
  50.                 int j = i;
  51.                 do {
  52.                     seen[j] = true;
  53.                     if (v[j] != i) moves.emplace_back(v[j], v[v[j]]);
  54.                     j = v[j];
  55.                 } while (j != i);
  56.             }
  57.         }
  58.         return moves;
  59.     };
  60.  
  61.     vector<pair<int, int>> moves = getMoves(perform(right)); // by value (not index)
  62.     while ((int)moves.size() < right) moves.emplace_back(0, 0);
  63.    
  64.     // simulate the moves
  65.     vector<int> where(n);
  66.     for (int i = 0; i < n; ++i) where[p[i]] = i;
  67.  
  68.     for (int i = 0; i < right; ++i) {
  69.         // perform the forced move
  70.         swap(p[x[i]], p[y[i]]);
  71.         swap(where[p[x[i]]], where[p[y[i]]]);
  72.  
  73.         // work out what positions correspond to the chosen move
  74.         cout << where[moves[i].first] << ' ' << where[moves[i].second] << endl;
  75.         swap(where[moves[i].first], where[moves[i].second]);
  76.         swap(p[where[moves[i].first]], p[where[moves[i].second]]);
  77.     }
  78.     return 0;
  79. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement