Advertisement
erek1e

IOI '05 P4 - Birthday

Jul 16th, 2022
825
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.50 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. int minMess(int n, vector<int> &p) {
  8.     vector<int> y(n); // index of value x in p
  9.     for (int i = 0; i < n; ++i) y[p[i]] = i;
  10.     // Binary search on mess
  11.     int left = -1, right = n;
  12.     while (left + 1 < right) {
  13.         int t = (left + right) / 2;
  14.         // See if possible with mess <= t
  15.         vector<int> shiftRange(1+n); // prefix sums
  16.         /* index of shiftRange represents how much to rotate target
  17.         permutation before placing it on initial permutation of 1, 2, .., n */
  18.         for (int x = 0; x < n; ++x) {
  19.             int l = y[x]-x-t, r = y[x]-x+t;
  20.             while (l < 0) l += n;
  21.             while (r < 0) r += n;
  22.             while (l >= n) l -= n;
  23.             while (r >= n) r -= n;
  24.             ++shiftRange[l], --shiftRange[r+1];
  25.             if (r < l) { // split into two ranges [l, n-1] and [0, r]
  26.                 ++shiftRange[0], --shiftRange[n];
  27.             }
  28.         }
  29.         bool intersection = false;
  30.         for (int i = 0; i < n; ++i) {
  31.             if (shiftRange[i] == n) intersection = true;
  32.             shiftRange[i+1] += shiftRange[i];
  33.         }
  34.  
  35.         if (intersection) right = t;
  36.         else left = t;
  37.     }
  38.     return right;
  39. }
  40.  
  41. int main() {
  42.     int n; cin >> n;
  43.     vector<int> p(n);
  44.     for (int &x : p) cin >> x, --x;
  45.     int a = minMess(n, p);
  46.     reverse(p.begin(), p.end());
  47.     int b = minMess(n, p);
  48.     cout << min(a, b) << endl;
  49.     return 0;
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement