| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 941985 | beaboss | Ancient Books (IOI17_books) | C++14 | 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.
// Source: https://oj.uz/problem/view/IOI17_books
//
#include "books.h"
#include "bits/stdc++.h"
using namespace std;
#define s second
#define f first
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<pii> vpii;
typedef vector<ll> vi;
#define FOR(i, a, b) for (ll i = (a); i<b; i++)
bool ckmin(ll& a, ll b){ return b < a ? a = b, true : false; }
bool ckmax(ll& a, ll b){ return b > a ? a = b, true : false; }
const ll N = 1e6 + 10;
ll ri[N], le[N];
bool vis[N];
vi nxt;
ll n;
ll l,r ;
void extend() {
ll ll = nxt[l];
while (ll < l && l > 0) {
l--;
ll = min(ll, nxt[l]);
}
ll rr = nxt[r];
while (r < rr && r < n-1) {
r++;
rr = max(rr, nxt[r]);
}
}
ll minimum_walk(vector<int> p, ll s) {
n = p.size();
l = r = s;
nxt = p;
ll ans = 0;
FOR(i, 0, n) ans += abs(i - p[i]);
ll st = 0;
for (;st < n;st++) if (p[st] != st) break;
ll en = n-1;
for (;en >= 0;en--) if (p[en] != en) break;
if (st >= en) return 0;
while (l > st || r < en) {
extend();
// cout << l << r << endl;
ll lo = l;
ll ro = r;
ll cr = 0;
while (l == lo && r < en) {
cr+=2;r++;
// cout << 'd' << endl;
extend();
}
bool rw = (nxt[r] < l);
ll fl = l, fr=r;
l = lo;r = ro;
ll cl = 0;
while (r == ro && l > st) {
// cout << l << endl;
cl+=2;l--;extend();
}
// cout << 'd' << endl;
bool lw = (nxt[l] > r);
l = min(l, fl);
r = max(r, fr);
// assert(lw ^ rw);
if (!lw || !rw) {
ans += cl + cr;
break;
}
ans += min(cl, cr);
}
return ans;
}
// int main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// // FOR(i, 0, 8) {
// // mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// // ll n = 100;
// // vi here(n);
// // FOR(i, 0, n) here[i] = i;
// // shuffle(here.begin(), here.end(), rng);
// // FOR(i, 0, n) cout << here[i] << ' ';
// // cout << endl;
// ll res = minimum_walk({0, 2, 4, 5, 1, 6, 3}, 0);
// cout << res << endl;
// }