| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 624612 |
2022-08-08T14:39:47 Z |
8e7 |
Ancient Books (IOI17_books) |
C++17 |
|
2000 ms |
34188 KB |
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 1000005
#define pii pair<int, int>
#define ff first
#define ss second
#include "books.h"
const int inf = 1e9;
pii ran[maxn], color[maxn];
long long minimum_walk(vector<int> p, int s) {
ll ans = 0;
int n = p.size();
vector<int> a(n, 0);
vector<bool> vis(n, 0);
{
int c = 0;
for (int i = 0;i < n;i++) {
ans += abs(p[i] - i);
if (!vis[i]) {
c++;
int cur = i;
int mi = inf, ma = 0;
do {
mi = min(mi, cur);
ma = max(ma, cur);
a[cur] = c;
vis[cur] = 1;
cur = p[cur];
} while (!vis[cur]);
color[c] = {mi, ma};
}
}
for (int i = 0;i < n;i++) ran[i] = color[a[i]];
}
int lb = 0, rb = n-1;
while (lb < s && p[lb] == lb) lb++;
while (rb > s && p[rb] == rb) rb--;
auto expand = [&] (int l, int r, int nl, int nr, int type) { //0:none, 1:left, 2:right
if (type == 1) {
l = max(lb, l-1);
nl = min(nl, ran[l].ff);
nr = max(nr, ran[l].ss);
} else if(type == 2) {
r = min(rb, r+1);
nl = min(nl, ran[r].ff);
nr = max(nr, ran[r].ss);
}
while (nl < l || nr > r) {
int tl = nl, tr = nr;
while (tl < l) {
l--;
nl = min(nl, ran[l].ff);
nr = max(nr, ran[l].ss);
}
while (tr > r) {
r++;
nl = min(nl, ran[r].ff);
nr = max(nr, ran[r].ss);
}
}
return make_pair(l, r);
};
pii cur = {s, s};
cur = expand(s, s, ran[s].ff, ran[s].ss, 0);
while (cur.ff > lb || cur.ss < rb) {
if (cur.ff == lb) {
cur = expand(cur.ff, cur.ss, cur.ff, cur.ss, 2);
ans+=2;
} else if (cur.ss == rb){
cur = expand(cur.ff, cur.ss, cur.ff, cur.ss, 1);
ans+=2;
} else {
pii tmp = cur, lef;
int sl = 0, sr = 0, vl, vr;
while (tmp.ss <= cur.ss) {
expand(tmp.ff, tmp.ss, tmp.ff, tmp.ss, 1);
sl++;
if (tmp.ff == lb) break;
}
vl = sl;
if (tmp.ss <= cur.ss) vl = inf;
lef = tmp;
tmp = cur;
while (tmp.ff >= cur.ff) {
expand(tmp.ff, tmp.ss, tmp.ff, tmp.ss, 2);
sr++;
if (tmp.ss == rb) break;
}
vr = sr;
if (tmp.ff >= cur.ff) vr = inf;
if (vl == inf && vr == inf) {
ans += 2 * (sl + sr);
break;
} else if (vl < vr) {
ans += 2 * vl;
cur = lef;
} else {
ans += 2 * vr;
cur = tmp;
}
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
308 KB |
Output is correct |
| 7 |
Correct |
1 ms |
316 KB |
Output is correct |
| 8 |
Correct |
1 ms |
312 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
312 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
312 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
0 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
312 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
308 KB |
Output is correct |
| 7 |
Correct |
1 ms |
316 KB |
Output is correct |
| 8 |
Correct |
1 ms |
312 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
312 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
312 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
0 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
312 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
340 KB |
Output is correct |
| 22 |
Correct |
1 ms |
312 KB |
Output is correct |
| 23 |
Correct |
1 ms |
340 KB |
Output is correct |
| 24 |
Correct |
1 ms |
308 KB |
Output is correct |
| 25 |
Correct |
1 ms |
340 KB |
Output is correct |
| 26 |
Correct |
0 ms |
340 KB |
Output is correct |
| 27 |
Correct |
1 ms |
340 KB |
Output is correct |
| 28 |
Correct |
1 ms |
340 KB |
Output is correct |
| 29 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
308 KB |
Output is correct |
| 7 |
Correct |
1 ms |
316 KB |
Output is correct |
| 8 |
Correct |
1 ms |
312 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
312 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
312 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
0 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
312 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
340 KB |
Output is correct |
| 22 |
Correct |
1 ms |
312 KB |
Output is correct |
| 23 |
Correct |
1 ms |
340 KB |
Output is correct |
| 24 |
Correct |
1 ms |
308 KB |
Output is correct |
| 25 |
Correct |
1 ms |
340 KB |
Output is correct |
| 26 |
Correct |
0 ms |
340 KB |
Output is correct |
| 27 |
Correct |
1 ms |
340 KB |
Output is correct |
| 28 |
Correct |
1 ms |
340 KB |
Output is correct |
| 29 |
Correct |
0 ms |
340 KB |
Output is correct |
| 30 |
Correct |
139 ms |
26164 KB |
Output is correct |
| 31 |
Correct |
139 ms |
26164 KB |
Output is correct |
| 32 |
Correct |
98 ms |
34188 KB |
Output is correct |
| 33 |
Correct |
105 ms |
31564 KB |
Output is correct |
| 34 |
Correct |
110 ms |
31560 KB |
Output is correct |
| 35 |
Correct |
107 ms |
30372 KB |
Output is correct |
| 36 |
Correct |
102 ms |
28152 KB |
Output is correct |
| 37 |
Correct |
104 ms |
26408 KB |
Output is correct |
| 38 |
Correct |
107 ms |
26204 KB |
Output is correct |
| 39 |
Correct |
105 ms |
26180 KB |
Output is correct |
| 40 |
Correct |
99 ms |
26060 KB |
Output is correct |
| 41 |
Correct |
113 ms |
26176 KB |
Output is correct |
| 42 |
Correct |
107 ms |
26172 KB |
Output is correct |
| 43 |
Correct |
123 ms |
31944 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2060 ms |
212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
308 KB |
Output is correct |
| 7 |
Correct |
1 ms |
316 KB |
Output is correct |
| 8 |
Correct |
1 ms |
312 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
312 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
312 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
0 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
312 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
340 KB |
Output is correct |
| 22 |
Correct |
1 ms |
312 KB |
Output is correct |
| 23 |
Correct |
1 ms |
340 KB |
Output is correct |
| 24 |
Correct |
1 ms |
308 KB |
Output is correct |
| 25 |
Correct |
1 ms |
340 KB |
Output is correct |
| 26 |
Correct |
0 ms |
340 KB |
Output is correct |
| 27 |
Correct |
1 ms |
340 KB |
Output is correct |
| 28 |
Correct |
1 ms |
340 KB |
Output is correct |
| 29 |
Correct |
0 ms |
340 KB |
Output is correct |
| 30 |
Correct |
139 ms |
26164 KB |
Output is correct |
| 31 |
Correct |
139 ms |
26164 KB |
Output is correct |
| 32 |
Correct |
98 ms |
34188 KB |
Output is correct |
| 33 |
Correct |
105 ms |
31564 KB |
Output is correct |
| 34 |
Correct |
110 ms |
31560 KB |
Output is correct |
| 35 |
Correct |
107 ms |
30372 KB |
Output is correct |
| 36 |
Correct |
102 ms |
28152 KB |
Output is correct |
| 37 |
Correct |
104 ms |
26408 KB |
Output is correct |
| 38 |
Correct |
107 ms |
26204 KB |
Output is correct |
| 39 |
Correct |
105 ms |
26180 KB |
Output is correct |
| 40 |
Correct |
99 ms |
26060 KB |
Output is correct |
| 41 |
Correct |
113 ms |
26176 KB |
Output is correct |
| 42 |
Correct |
107 ms |
26172 KB |
Output is correct |
| 43 |
Correct |
123 ms |
31944 KB |
Output is correct |
| 44 |
Execution timed out |
2060 ms |
212 KB |
Time limit exceeded |
| 45 |
Halted |
0 ms |
0 KB |
- |
