#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;
void dfs(int x){
li[x]=true;
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;
}
for(int i=1;i<=n;i++){
if(!li[i]){
if(p[i]!=i)last=i;
mins=n; maxs=1;
dfs(i);
pref[mins]++; pref[maxs]--;
}
}
for(int i=1;i<=n;i++)li[i]=false;
for(int i=n;i>=1;i--){
if(!li[i]){
if(p[i]!=i)fr=i;
dfs(i);
}
}
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>=1;i--){
curr+=pref[i];
if(i>s)continue;
if(curr==0 and fr<i)ans+=2;
}
return ans;
}
/*int main(){
cout<<minimum_walk({0, 2, 3, 1}, 0)<<"\n";
return 0;
}*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4432 KB |
Output is correct |
2 |
Correct |
1 ms |
4432 KB |
Output is correct |
3 |
Correct |
1 ms |
4608 KB |
Output is correct |
4 |
Correct |
1 ms |
4432 KB |
Output is correct |
5 |
Correct |
1 ms |
4432 KB |
Output is correct |
6 |
Correct |
1 ms |
4432 KB |
Output is correct |
7 |
Correct |
1 ms |
4432 KB |
Output is correct |
8 |
Correct |
2 ms |
4432 KB |
Output is correct |
9 |
Incorrect |
1 ms |
4432 KB |
3rd lines differ - on the 1st token, expected: '0', found: '2' |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4432 KB |
Output is correct |
2 |
Correct |
1 ms |
4432 KB |
Output is correct |
3 |
Correct |
1 ms |
4608 KB |
Output is correct |
4 |
Correct |
1 ms |
4432 KB |
Output is correct |
5 |
Correct |
1 ms |
4432 KB |
Output is correct |
6 |
Correct |
1 ms |
4432 KB |
Output is correct |
7 |
Correct |
1 ms |
4432 KB |
Output is correct |
8 |
Correct |
2 ms |
4432 KB |
Output is correct |
9 |
Incorrect |
1 ms |
4432 KB |
3rd lines differ - on the 1st token, expected: '0', found: '2' |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4432 KB |
Output is correct |
2 |
Correct |
1 ms |
4432 KB |
Output is correct |
3 |
Correct |
1 ms |
4608 KB |
Output is correct |
4 |
Correct |
1 ms |
4432 KB |
Output is correct |
5 |
Correct |
1 ms |
4432 KB |
Output is correct |
6 |
Correct |
1 ms |
4432 KB |
Output is correct |
7 |
Correct |
1 ms |
4432 KB |
Output is correct |
8 |
Correct |
2 ms |
4432 KB |
Output is correct |
9 |
Incorrect |
1 ms |
4432 KB |
3rd lines differ - on the 1st token, expected: '0', found: '2' |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
4432 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 |
1 ms |
4432 KB |
Output is correct |
2 |
Correct |
1 ms |
4432 KB |
Output is correct |
3 |
Correct |
1 ms |
4608 KB |
Output is correct |
4 |
Correct |
1 ms |
4432 KB |
Output is correct |
5 |
Correct |
1 ms |
4432 KB |
Output is correct |
6 |
Correct |
1 ms |
4432 KB |
Output is correct |
7 |
Correct |
1 ms |
4432 KB |
Output is correct |
8 |
Correct |
2 ms |
4432 KB |
Output is correct |
9 |
Incorrect |
1 ms |
4432 KB |
3rd lines differ - on the 1st token, expected: '0', found: '2' |
10 |
Halted |
0 ms |
0 KB |
- |