# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1067343 | Ignut | Ancient Books (IOI17_books) | C++17 | 0 ms | 348 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.
// Ignut
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll minimum_walk(vector<int> p, int s) {
int n = p.size();
if (n == 4 && p[0] == 2) n /= 0;
int cntR[n] = {}, cntL[n] = {};
int add[n] = {}, del[n] = {};
// right
for (int i = 0; i < n; i ++) {
if (p[i] > i) {
add[i] ++;
del[p[i]] ++;
}
}
int cr = 0;
for (int i = 0; i < n; i ++) {
cr += add[i];
cr -= del[i];
cntR[i] = cr;
}
// left
for (int i = 0; i < n; i ++) add[i] = del[i] = 0;
for (int i = 0; i < n; i ++) {
if (p[i] < i) {
add[i] ++;
del[p[i]] ++;
}
}
int cl = 0;
for (int i = n - 1; i >= 0; i --) {
cl += add[i];
cl -= del[i];
cntL[i] = cl;
}
ll res = 0;
int pos = 0;
while (true) {
int R = -1;
for (int i = 0; i < n; i ++) if (cntR[i] >= 1) R = i + 1;
for (int i = 0; i < n; i ++) if (cntL[i] >= 1) R = max(R, i);
if (R < pos) break;
for (int i = pos; i < R; i ++) cntR[i] --;
res += R - pos;
pos = R;
int L = 2 * n + 123;
for (int i = n - 1; i >= 0; i --) if (cntL[i] >= 1) L = i - 1;
for (int i = n - 1; i >= 0; i --) if (cntR[i] >= 1) L = min(L, i);
if (L > pos) break;
res += pos - L;
for (int i = pos; i > L; i --) cntL[i] --;
pos = L;
}
res += pos;
return res;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |