# IOI '05 P4 - Birthday

Jul 16th, 2022
825
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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. }