#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e6;
const ll inf = 2e9;
bool vis[N];
vector <int> points;
int l[N],r[N];
long long minimum_walk(std::vector<int> p, int s) {
int n = p.size();
ll ans = 0;
ll mn2 = s;
ll mx2 = s;
for(ll i = 0;i < n;i++){
ans+=abs(i - p[i]);
if(i != p[i]){
mx2 = max(mx2,i);
mn2 = min(mn2,i);
}
if(!vis[i]){
points.clear();
int nr = i;
int mx = -inf;
int mn = inf;
while(!vis[nr]){
vis[nr] = 1;
mx = max(mx,nr);
mn = min(mn,nr);
points.push_back(nr);
nr = p[nr];
}
for(auto j:points){
l[j] = mn;
r[j] = mx;
}
}
}
int curl,curr,exl,exr;
curl = s;exl = l[s];
curr = s;exr = r[s];
//cout<<mn2<<' '<<mx2<<' '<<exl<<' '<<exr<<' '<<curl<<' '<<curr<<'\n';
while(exl > mn2 || exr < mx2){
if(curl > exl){
curl--;
exl = min(exl,l[curl]);
exr = max(exr,r[curl]);
}else if(curr < exr){
curr++;
exl = min(exl,l[curr]);
exr = max(exr,r[curr]);
}else{
int costl = 0;
bool ok = 0;
int x = exl;
int exl2 = exl;
while(x > mn2){
if(r[x] > exr){
ok = 1;
break;
}
exl2 = min(exl2,l[x]);
if(x == exl2){
costl+=2;
exl2--;
}
x--;
}
int costr = 0;
int exr2 = exr;
x = exr;
while(x < mx2){
if(l[x] < exl){
ok = 1;
break;
}
exr2 = max(exr2,r[x]);
if(x == exr2){
costr+=2;
exr2++;
}
x++;
}
if(ok){
if(costl > costr){
exr = exr2;
ans+=costr;
}else{
exl = exl2;
ans+=costl;
}
}else{
ans+=costl;
ans+=costr;
break;
}
}
}
//cout<<ans<<'\n';
return ans;
}
/**
7 3
6 1 2 3 4 5 0
7 3
2 1 0 3 6 5 4
**/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
2 ms |
4444 KB |
Output is correct |
6 |
Correct |
2 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4440 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4444 KB |
Output is correct |
10 |
Correct |
2 ms |
4444 KB |
Output is correct |
11 |
Correct |
1 ms |
4444 KB |
Output is correct |
12 |
Correct |
1 ms |
4444 KB |
Output is correct |
13 |
Correct |
1 ms |
4444 KB |
Output is correct |
14 |
Correct |
1 ms |
4444 KB |
Output is correct |
15 |
Correct |
1 ms |
4552 KB |
Output is correct |
16 |
Correct |
1 ms |
4444 KB |
Output is correct |
17 |
Correct |
1 ms |
4444 KB |
Output is correct |
18 |
Correct |
1 ms |
4444 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
2 ms |
4444 KB |
Output is correct |
6 |
Correct |
2 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4440 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4444 KB |
Output is correct |
10 |
Correct |
2 ms |
4444 KB |
Output is correct |
11 |
Correct |
1 ms |
4444 KB |
Output is correct |
12 |
Correct |
1 ms |
4444 KB |
Output is correct |
13 |
Correct |
1 ms |
4444 KB |
Output is correct |
14 |
Correct |
1 ms |
4444 KB |
Output is correct |
15 |
Correct |
1 ms |
4552 KB |
Output is correct |
16 |
Correct |
1 ms |
4444 KB |
Output is correct |
17 |
Correct |
1 ms |
4444 KB |
Output is correct |
18 |
Correct |
1 ms |
4444 KB |
Output is correct |
19 |
Correct |
1 ms |
4444 KB |
Output is correct |
20 |
Correct |
1 ms |
4444 KB |
Output is correct |
21 |
Correct |
1 ms |
4444 KB |
Output is correct |
22 |
Correct |
1 ms |
4444 KB |
Output is correct |
23 |
Correct |
1 ms |
4444 KB |
Output is correct |
24 |
Correct |
1 ms |
4444 KB |
Output is correct |
25 |
Correct |
1 ms |
4444 KB |
Output is correct |
26 |
Correct |
1 ms |
4444 KB |
Output is correct |
27 |
Correct |
1 ms |
4704 KB |
Output is correct |
28 |
Correct |
1 ms |
4444 KB |
Output is correct |
29 |
Correct |
1 ms |
4544 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
2 ms |
4444 KB |
Output is correct |
6 |
Correct |
2 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4440 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4444 KB |
Output is correct |
10 |
Correct |
2 ms |
4444 KB |
Output is correct |
11 |
Correct |
1 ms |
4444 KB |
Output is correct |
12 |
Correct |
1 ms |
4444 KB |
Output is correct |
13 |
Correct |
1 ms |
4444 KB |
Output is correct |
14 |
Correct |
1 ms |
4444 KB |
Output is correct |
15 |
Correct |
1 ms |
4552 KB |
Output is correct |
16 |
Correct |
1 ms |
4444 KB |
Output is correct |
17 |
Correct |
1 ms |
4444 KB |
Output is correct |
18 |
Correct |
1 ms |
4444 KB |
Output is correct |
19 |
Correct |
1 ms |
4444 KB |
Output is correct |
20 |
Correct |
1 ms |
4444 KB |
Output is correct |
21 |
Correct |
1 ms |
4444 KB |
Output is correct |
22 |
Correct |
1 ms |
4444 KB |
Output is correct |
23 |
Correct |
1 ms |
4444 KB |
Output is correct |
24 |
Correct |
1 ms |
4444 KB |
Output is correct |
25 |
Correct |
1 ms |
4444 KB |
Output is correct |
26 |
Correct |
1 ms |
4444 KB |
Output is correct |
27 |
Correct |
1 ms |
4704 KB |
Output is correct |
28 |
Correct |
1 ms |
4444 KB |
Output is correct |
29 |
Correct |
1 ms |
4544 KB |
Output is correct |
30 |
Correct |
106 ms |
27568 KB |
Output is correct |
31 |
Correct |
99 ms |
25324 KB |
Output is correct |
32 |
Correct |
74 ms |
23680 KB |
Output is correct |
33 |
Correct |
84 ms |
23892 KB |
Output is correct |
34 |
Correct |
82 ms |
23636 KB |
Output is correct |
35 |
Correct |
85 ms |
23636 KB |
Output is correct |
36 |
Correct |
89 ms |
23660 KB |
Output is correct |
37 |
Correct |
89 ms |
23660 KB |
Output is correct |
38 |
Correct |
78 ms |
23684 KB |
Output is correct |
39 |
Correct |
79 ms |
23788 KB |
Output is correct |
40 |
Correct |
82 ms |
24016 KB |
Output is correct |
41 |
Correct |
95 ms |
25544 KB |
Output is correct |
42 |
Correct |
89 ms |
24512 KB |
Output is correct |
43 |
Correct |
78 ms |
23636 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4700 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4440 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
11 |
Incorrect |
1 ms |
4536 KB |
3rd lines differ - on the 1st token, expected: '446014', found: '446016' |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
2 ms |
4444 KB |
Output is correct |
6 |
Correct |
2 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4440 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4444 KB |
Output is correct |
10 |
Correct |
2 ms |
4444 KB |
Output is correct |
11 |
Correct |
1 ms |
4444 KB |
Output is correct |
12 |
Correct |
1 ms |
4444 KB |
Output is correct |
13 |
Correct |
1 ms |
4444 KB |
Output is correct |
14 |
Correct |
1 ms |
4444 KB |
Output is correct |
15 |
Correct |
1 ms |
4552 KB |
Output is correct |
16 |
Correct |
1 ms |
4444 KB |
Output is correct |
17 |
Correct |
1 ms |
4444 KB |
Output is correct |
18 |
Correct |
1 ms |
4444 KB |
Output is correct |
19 |
Correct |
1 ms |
4444 KB |
Output is correct |
20 |
Correct |
1 ms |
4444 KB |
Output is correct |
21 |
Correct |
1 ms |
4444 KB |
Output is correct |
22 |
Correct |
1 ms |
4444 KB |
Output is correct |
23 |
Correct |
1 ms |
4444 KB |
Output is correct |
24 |
Correct |
1 ms |
4444 KB |
Output is correct |
25 |
Correct |
1 ms |
4444 KB |
Output is correct |
26 |
Correct |
1 ms |
4444 KB |
Output is correct |
27 |
Correct |
1 ms |
4704 KB |
Output is correct |
28 |
Correct |
1 ms |
4444 KB |
Output is correct |
29 |
Correct |
1 ms |
4544 KB |
Output is correct |
30 |
Correct |
106 ms |
27568 KB |
Output is correct |
31 |
Correct |
99 ms |
25324 KB |
Output is correct |
32 |
Correct |
74 ms |
23680 KB |
Output is correct |
33 |
Correct |
84 ms |
23892 KB |
Output is correct |
34 |
Correct |
82 ms |
23636 KB |
Output is correct |
35 |
Correct |
85 ms |
23636 KB |
Output is correct |
36 |
Correct |
89 ms |
23660 KB |
Output is correct |
37 |
Correct |
89 ms |
23660 KB |
Output is correct |
38 |
Correct |
78 ms |
23684 KB |
Output is correct |
39 |
Correct |
79 ms |
23788 KB |
Output is correct |
40 |
Correct |
82 ms |
24016 KB |
Output is correct |
41 |
Correct |
95 ms |
25544 KB |
Output is correct |
42 |
Correct |
89 ms |
24512 KB |
Output is correct |
43 |
Correct |
78 ms |
23636 KB |
Output is correct |
44 |
Correct |
1 ms |
4444 KB |
Output is correct |
45 |
Correct |
1 ms |
4444 KB |
Output is correct |
46 |
Correct |
1 ms |
4444 KB |
Output is correct |
47 |
Correct |
1 ms |
4444 KB |
Output is correct |
48 |
Correct |
1 ms |
4444 KB |
Output is correct |
49 |
Correct |
1 ms |
4444 KB |
Output is correct |
50 |
Correct |
1 ms |
4700 KB |
Output is correct |
51 |
Correct |
1 ms |
4444 KB |
Output is correct |
52 |
Correct |
1 ms |
4440 KB |
Output is correct |
53 |
Correct |
1 ms |
4444 KB |
Output is correct |
54 |
Incorrect |
1 ms |
4536 KB |
3rd lines differ - on the 1st token, expected: '446014', found: '446016' |
55 |
Halted |
0 ms |
0 KB |
- |