| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 684055 | piOOE | Ancient Books (IOI17_books) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "books.h"
using namespace std;
using ll = long long;
long long minimum_walk(std::vector<int> p, int s) {
if (is_sorted(p.begin(), p.end())) {
return 0;
}
int n = p.size();
ll ans = 0;
vector<int> inv(n);
for (int i = 0; i < n; ++i) {
inv[p[i]] = i;
ans += abs(p[i] - i);
}
vector<int> lx(n, -1), rx(n, -1);
for (int i = 0; i < n; ++i) {
if (lx[i] == -1) {
int v = i, mn = n, mx = 0;
vector<int> cycle;
do {
mn = min(mn, v);
mx = max(mx, v);
lx[v] = 228;
cycle.push_back(v);
v = p[v];
} while (lx[v] == -1);
for (int x: cycle) {
lx[x] = mn, rx[x] = mx;
}
}
}
auto extend = [&](int &l, int &r, int limL, int limR) {
int mn = l, mx = r;
for (int i = l; i <= limL; ++i) {
mn = min(mn, lx[i]);
mx = max(mx, rx[i]);
}
for (int i = limR; i <= r; ++i) {
mn = min(mn, lx[i]);
mx = max(mx, rx[i]);
}
l = mn, r = mx;
};
int trivL = 0, trivR = n - 1;
while (p[trivL] == trivL) {
trivL += 1;
}
while (p[trivR] == trivR) {
trivR -= 1;
}
int l = lx[s], r = rx[s];
extend(l, r, s, s);
while (l >= 0 && r < n) {
int cl = l, cr = r;
int ansL = 0, ansR = 0;
int mn = n;
bool found = false;
while (cl > 0) {
cl -= 1;
if (mn > cl) {
ansL += 1;
}
mn = min(mn, p[cl]);
if (rx[cl] > r) {
found = true;
break;
}
}
int mx = 0;
while (cr < n - 1) {
cr += 1;
if (mx < cr) {
ansR += 1;
}
mx = max(mx, p[cr]);
if (lx[cr] < l) {
found = true;
break;
}
}
if (!found) {
if (trivL < l) {
ans += (ansL - trivL) * 2;
}
if (trivR > r) {
ans += (ansR - (n - trivR - 1)) * 2;
}
break;
}
ans += min(ansL, ansR) * 2;
int pl = l, pr = r;
l = min(lx[cl], lx[cr]);
r = max(rx[cr], rx[cr]);
extend(l, r, pl, pr);
}
return ans;
}