#include<bits/stdc++.h>
#define MAXN 1000007
using namespace std;
int n,s,p[MAXN],fr,last,mins,maxs,pref[MAXN],curr;
bool li[MAXN];
long long ans;
int k,cycle[MAXN];
pair<int,int> where[MAXN];
void dfs(int x){
li[x]=true;
cycle[x]=k;
ans+=abs(x-p[x]);
mins=min(mins,x);
maxs=max(maxs,x);
if(!li[p[x]])dfs(p[x]);
}
long long minimum_walk(vector<int> P, int S){
n=int(P.size()); s=S+1;
for(int i=1;i<=n;i++){
p[i]=P[i-1]+1;
}
last=0; fr=n+1;
for(int i=1;i<=n;i++){
if(!li[i]){
if(p[i]!=i)last=i;
dfs(i);
}
}
for(int i=1;i<=n;i++)li[i]=false;
for(int i=n;i>=1;i--){
if(!li[i]){
k++;
if(p[i]!=i)fr=i;
mins=n; maxs=1;
dfs(i);
where[k]={mins,maxs};
pref[mins]++; pref[maxs]--;
}
}
ans/=2;
for(int i=1;i<=n-1;i++){
curr+=pref[i];
if(i<s)continue;
if(curr==0 and last>i)ans+=2;
}
curr=0;
for(int i=n;i>=2;i--){
curr+=pref[i];
if(i>s)continue;
if(curr==0 and fr<i)ans+=2;
}
/// more steps inside initial cycle
vector<int> l,r;
int pt=s;
while(pt<n){
int t=0;
pt=where[cycle[pt]].second+1;
t++;
while(pt<=n and where[cycle[pt]].first>=s){
if(where[cycle[pt]].second==pt){
pt++; t++;
}else{
pt=where[cycle[pt]].second;
}
}
if(pt<=n)r.push_back(t);
}
pt=s;
while(pt>1){
int t=0;
pt=where[cycle[pt]].first-1;
t++;
while(pt>=1 and where[cycle[pt]].second<=s){
if(where[cycle[pt]].first==pt){
pt--; t++;
}else{
pt=where[cycle[pt]].first;
}
}
if(pt>=1)l.push_back(t);
}
if(l.size()!=r.size())cout<<1/0;
for(int i=0;i<l.size();i++){
ans+=min(l[i],r[i]);
}
return ans;
}
/*int main(){
cout<<minimum_walk({12,1,9,3,7,5,6,4,8,2,11,10,0},6)<<"\n";
return 0;
}*/
Compilation message
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:109:31: warning: division by zero [-Wdiv-by-zero]
109 | if(l.size()!=r.size())cout<<1/0;
| ~^~
books.cpp:111:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for(int i=0;i<l.size();i++){
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6480 KB |
Output is correct |
2 |
Correct |
2 ms |
6480 KB |
Output is correct |
3 |
Correct |
2 ms |
6480 KB |
Output is correct |
4 |
Correct |
2 ms |
6480 KB |
Output is correct |
5 |
Correct |
2 ms |
6480 KB |
Output is correct |
6 |
Correct |
1 ms |
6612 KB |
Output is correct |
7 |
Correct |
1 ms |
6480 KB |
Output is correct |
8 |
Correct |
2 ms |
6480 KB |
Output is correct |
9 |
Correct |
2 ms |
6772 KB |
Output is correct |
10 |
Correct |
1 ms |
6480 KB |
Output is correct |
11 |
Correct |
2 ms |
6480 KB |
Output is correct |
12 |
Correct |
2 ms |
6480 KB |
Output is correct |
13 |
Correct |
1 ms |
6480 KB |
Output is correct |
14 |
Correct |
2 ms |
6480 KB |
Output is correct |
15 |
Correct |
2 ms |
6592 KB |
Output is correct |
16 |
Correct |
2 ms |
6604 KB |
Output is correct |
17 |
Correct |
1 ms |
6480 KB |
Output is correct |
18 |
Correct |
1 ms |
6480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6480 KB |
Output is correct |
2 |
Correct |
2 ms |
6480 KB |
Output is correct |
3 |
Correct |
2 ms |
6480 KB |
Output is correct |
4 |
Correct |
2 ms |
6480 KB |
Output is correct |
5 |
Correct |
2 ms |
6480 KB |
Output is correct |
6 |
Correct |
1 ms |
6612 KB |
Output is correct |
7 |
Correct |
1 ms |
6480 KB |
Output is correct |
8 |
Correct |
2 ms |
6480 KB |
Output is correct |
9 |
Correct |
2 ms |
6772 KB |
Output is correct |
10 |
Correct |
1 ms |
6480 KB |
Output is correct |
11 |
Correct |
2 ms |
6480 KB |
Output is correct |
12 |
Correct |
2 ms |
6480 KB |
Output is correct |
13 |
Correct |
1 ms |
6480 KB |
Output is correct |
14 |
Correct |
2 ms |
6480 KB |
Output is correct |
15 |
Correct |
2 ms |
6592 KB |
Output is correct |
16 |
Correct |
2 ms |
6604 KB |
Output is correct |
17 |
Correct |
1 ms |
6480 KB |
Output is correct |
18 |
Correct |
1 ms |
6480 KB |
Output is correct |
19 |
Correct |
2 ms |
6480 KB |
Output is correct |
20 |
Correct |
2 ms |
6480 KB |
Output is correct |
21 |
Correct |
2 ms |
6480 KB |
Output is correct |
22 |
Correct |
1 ms |
6480 KB |
Output is correct |
23 |
Correct |
1 ms |
6480 KB |
Output is correct |
24 |
Correct |
1 ms |
6596 KB |
Output is correct |
25 |
Correct |
2 ms |
6480 KB |
Output is correct |
26 |
Correct |
2 ms |
6480 KB |
Output is correct |
27 |
Correct |
2 ms |
6480 KB |
Output is correct |
28 |
Correct |
2 ms |
6480 KB |
Output is correct |
29 |
Correct |
2 ms |
6652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6480 KB |
Output is correct |
2 |
Correct |
2 ms |
6480 KB |
Output is correct |
3 |
Correct |
2 ms |
6480 KB |
Output is correct |
4 |
Correct |
2 ms |
6480 KB |
Output is correct |
5 |
Correct |
2 ms |
6480 KB |
Output is correct |
6 |
Correct |
1 ms |
6612 KB |
Output is correct |
7 |
Correct |
1 ms |
6480 KB |
Output is correct |
8 |
Correct |
2 ms |
6480 KB |
Output is correct |
9 |
Correct |
2 ms |
6772 KB |
Output is correct |
10 |
Correct |
1 ms |
6480 KB |
Output is correct |
11 |
Correct |
2 ms |
6480 KB |
Output is correct |
12 |
Correct |
2 ms |
6480 KB |
Output is correct |
13 |
Correct |
1 ms |
6480 KB |
Output is correct |
14 |
Correct |
2 ms |
6480 KB |
Output is correct |
15 |
Correct |
2 ms |
6592 KB |
Output is correct |
16 |
Correct |
2 ms |
6604 KB |
Output is correct |
17 |
Correct |
1 ms |
6480 KB |
Output is correct |
18 |
Correct |
1 ms |
6480 KB |
Output is correct |
19 |
Correct |
2 ms |
6480 KB |
Output is correct |
20 |
Correct |
2 ms |
6480 KB |
Output is correct |
21 |
Correct |
2 ms |
6480 KB |
Output is correct |
22 |
Correct |
1 ms |
6480 KB |
Output is correct |
23 |
Correct |
1 ms |
6480 KB |
Output is correct |
24 |
Correct |
1 ms |
6596 KB |
Output is correct |
25 |
Correct |
2 ms |
6480 KB |
Output is correct |
26 |
Correct |
2 ms |
6480 KB |
Output is correct |
27 |
Correct |
2 ms |
6480 KB |
Output is correct |
28 |
Correct |
2 ms |
6480 KB |
Output is correct |
29 |
Correct |
2 ms |
6652 KB |
Output is correct |
30 |
Correct |
123 ms |
25848 KB |
Output is correct |
31 |
Correct |
125 ms |
24128 KB |
Output is correct |
32 |
Correct |
92 ms |
32252 KB |
Output is correct |
33 |
Correct |
104 ms |
32380 KB |
Output is correct |
34 |
Correct |
110 ms |
35004 KB |
Output is correct |
35 |
Correct |
106 ms |
32376 KB |
Output is correct |
36 |
Correct |
101 ms |
28232 KB |
Output is correct |
37 |
Correct |
90 ms |
30024 KB |
Output is correct |
38 |
Correct |
89 ms |
27644 KB |
Output is correct |
39 |
Correct |
97 ms |
25800 KB |
Output is correct |
40 |
Correct |
92 ms |
24904 KB |
Output is correct |
41 |
Correct |
108 ms |
26936 KB |
Output is correct |
42 |
Correct |
106 ms |
26952 KB |
Output is correct |
43 |
Correct |
90 ms |
32172 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
12 ms |
12880 KB |
Execution killed with signal 8 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6480 KB |
Output is correct |
2 |
Correct |
2 ms |
6480 KB |
Output is correct |
3 |
Correct |
2 ms |
6480 KB |
Output is correct |
4 |
Correct |
2 ms |
6480 KB |
Output is correct |
5 |
Correct |
2 ms |
6480 KB |
Output is correct |
6 |
Correct |
1 ms |
6612 KB |
Output is correct |
7 |
Correct |
1 ms |
6480 KB |
Output is correct |
8 |
Correct |
2 ms |
6480 KB |
Output is correct |
9 |
Correct |
2 ms |
6772 KB |
Output is correct |
10 |
Correct |
1 ms |
6480 KB |
Output is correct |
11 |
Correct |
2 ms |
6480 KB |
Output is correct |
12 |
Correct |
2 ms |
6480 KB |
Output is correct |
13 |
Correct |
1 ms |
6480 KB |
Output is correct |
14 |
Correct |
2 ms |
6480 KB |
Output is correct |
15 |
Correct |
2 ms |
6592 KB |
Output is correct |
16 |
Correct |
2 ms |
6604 KB |
Output is correct |
17 |
Correct |
1 ms |
6480 KB |
Output is correct |
18 |
Correct |
1 ms |
6480 KB |
Output is correct |
19 |
Correct |
2 ms |
6480 KB |
Output is correct |
20 |
Correct |
2 ms |
6480 KB |
Output is correct |
21 |
Correct |
2 ms |
6480 KB |
Output is correct |
22 |
Correct |
1 ms |
6480 KB |
Output is correct |
23 |
Correct |
1 ms |
6480 KB |
Output is correct |
24 |
Correct |
1 ms |
6596 KB |
Output is correct |
25 |
Correct |
2 ms |
6480 KB |
Output is correct |
26 |
Correct |
2 ms |
6480 KB |
Output is correct |
27 |
Correct |
2 ms |
6480 KB |
Output is correct |
28 |
Correct |
2 ms |
6480 KB |
Output is correct |
29 |
Correct |
2 ms |
6652 KB |
Output is correct |
30 |
Correct |
123 ms |
25848 KB |
Output is correct |
31 |
Correct |
125 ms |
24128 KB |
Output is correct |
32 |
Correct |
92 ms |
32252 KB |
Output is correct |
33 |
Correct |
104 ms |
32380 KB |
Output is correct |
34 |
Correct |
110 ms |
35004 KB |
Output is correct |
35 |
Correct |
106 ms |
32376 KB |
Output is correct |
36 |
Correct |
101 ms |
28232 KB |
Output is correct |
37 |
Correct |
90 ms |
30024 KB |
Output is correct |
38 |
Correct |
89 ms |
27644 KB |
Output is correct |
39 |
Correct |
97 ms |
25800 KB |
Output is correct |
40 |
Correct |
92 ms |
24904 KB |
Output is correct |
41 |
Correct |
108 ms |
26936 KB |
Output is correct |
42 |
Correct |
106 ms |
26952 KB |
Output is correct |
43 |
Correct |
90 ms |
32172 KB |
Output is correct |
44 |
Runtime error |
12 ms |
12880 KB |
Execution killed with signal 8 |
45 |
Halted |
0 ms |
0 KB |
- |