#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll INF = 1e8;
//#include "books.h"
ll minimum_walk(vector<int> p, int s) {
ll N = p.size();
ll flux[N];
for (ll i=0;i<N;i++) {
flux[i]=0;
}
for (ll i=0;i<N;i++) {
if (p[i]>i) {
flux[i]++;
flux[p[i]]--;
}
}
ll pf[N+1];
pf[0]=0;
ll ans = 0;
for (ll i=0;i<N;i++) {
pf[i+1]=pf[i]+flux[i];
//cout << "x="<<(i+1)<<", pf[x]="<<pf[i+1]<<"\n";
if (pf[i+1]>1) {
ans += 2*(pf[i+1]-1);
}
}
ll maxl[N+1]; ll minl[N+1];
for (ll i=0;i<=N;i++) {
maxl[i]=-INF;
minl[i]=INF;
}
for (ll i=1;i<=N;i++) {
maxl[pf[i]]=max(maxl[pf[i]],i);
minl[pf[i]]=min(minl[pf[i]],i-1);
}
for (ll i=N;i>=1;i--) {
maxl[i-1]=max(maxl[i],maxl[i-1]);
minl[i-1]=min(minl[i],minl[i-1]);
}
//ll xc = 0;
/*for (ll i=1;i<=N;i++) {
//cout << "i="<<i<<", maxl="<<maxl[i]<<", minl="<<minl[i]<<"\n";
if (minl[i]!=INF) {
//ans += abs(xc-minl[i]);
//xc = minl[i];
//ans += abs(xc-maxl[i]);
//xc = maxl[i];
ans += 2*(maxl[i]-minl[i]);
if (i==1) {
if (s<minl[i]) {
ans += 2*(minl[i]-s);
} else if (s>maxl[i]) {
ans += 2*(maxl[i]-s);
}
}
}
}*/
if (minl[1]!=INF) {
ans += 2*(maxl[1]-minl[1]);
if (s<minl[1]) {
ans += 2*(minl[1]-s);
} else if (s>maxl[1]) {
ans += 2*(maxl[1]-s);
}
}
//ans += abs(xc);
return ans;
}
/*int main() {
vector<int> p1 = {1,0,2,6,5,4,3};
cout << minimum_walk(p1,0);
}*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
344 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
344 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
1 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
604 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
1 ms |
348 KB |
Output is correct |
29 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
344 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
1 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
604 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
1 ms |
348 KB |
Output is correct |
29 |
Correct |
0 ms |
344 KB |
Output is correct |
30 |
Correct |
92 ms |
46176 KB |
Output is correct |
31 |
Correct |
106 ms |
46164 KB |
Output is correct |
32 |
Correct |
89 ms |
46052 KB |
Output is correct |
33 |
Correct |
91 ms |
46060 KB |
Output is correct |
34 |
Correct |
89 ms |
46048 KB |
Output is correct |
35 |
Correct |
95 ms |
46164 KB |
Output is correct |
36 |
Correct |
91 ms |
46160 KB |
Output is correct |
37 |
Correct |
89 ms |
46160 KB |
Output is correct |
38 |
Correct |
102 ms |
46164 KB |
Output is correct |
39 |
Correct |
86 ms |
46164 KB |
Output is correct |
40 |
Correct |
88 ms |
46160 KB |
Output is correct |
41 |
Correct |
93 ms |
46052 KB |
Output is correct |
42 |
Correct |
92 ms |
46176 KB |
Output is correct |
43 |
Correct |
90 ms |
46164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '2744' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
344 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
1 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
604 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
1 ms |
348 KB |
Output is correct |
29 |
Correct |
0 ms |
344 KB |
Output is correct |
30 |
Correct |
92 ms |
46176 KB |
Output is correct |
31 |
Correct |
106 ms |
46164 KB |
Output is correct |
32 |
Correct |
89 ms |
46052 KB |
Output is correct |
33 |
Correct |
91 ms |
46060 KB |
Output is correct |
34 |
Correct |
89 ms |
46048 KB |
Output is correct |
35 |
Correct |
95 ms |
46164 KB |
Output is correct |
36 |
Correct |
91 ms |
46160 KB |
Output is correct |
37 |
Correct |
89 ms |
46160 KB |
Output is correct |
38 |
Correct |
102 ms |
46164 KB |
Output is correct |
39 |
Correct |
86 ms |
46164 KB |
Output is correct |
40 |
Correct |
88 ms |
46160 KB |
Output is correct |
41 |
Correct |
93 ms |
46052 KB |
Output is correct |
42 |
Correct |
92 ms |
46176 KB |
Output is correct |
43 |
Correct |
90 ms |
46164 KB |
Output is correct |
44 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '2744' |
45 |
Halted |
0 ms |
0 KB |
- |