#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]);
}
int dp[1007][1007];
bool vis[1007][1007];
int ff(int l,int r){
if(l==1 and r==n)return 0;
if(vis[l][r])return dp[l][r];
vis[l][r]=true;
dp[l][r]=2*n;
if(l>1){
int from=l-1,to=r,ll=l-1,rr=r+1;
while(ll>=from or rr<=to){
while(ll>=from){
from=min(from,where[cycle[ll]].first);
to=max(to,where[cycle[ll]].second);
ll--;
}
while(rr<=to){
from=min(from,where[cycle[rr]].first);
to=max(to,where[cycle[rr]].second);
rr++;
}
}
dp[l][r]=min(dp[l][r],ff(from,to)+2);
}
if(r<n){
int from=l,to=r+1,ll=l-1,rr=r+1;
while(ll>=from or rr<=to){
while(ll>=from){
from=min(from,where[cycle[ll]].first);
to=max(to,where[cycle[ll]].second);
ll--;
}
while(rr<=to){
from=min(from,where[cycle[rr]].first);
to=max(to,where[cycle[rr]].second);
rr++;
}
}
dp[l][r]=min(dp[l][r],ff(from,to)+2);
}
return dp[l][r];
}
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;
li[i]=false; pref[i]=0;
}
last=0; fr=n+1; k=0; ans=0;
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;
/// more steps inside initial cycle
if(s!=1)ans+=ff(s,s);
else{
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;
}
}
return ans;
}
/*int main(){
vector<int> perm;
for(int i=0;i<10;i++){
perm.push_back(i);
}
while(true){
random_shuffle(perm.begin(),perm.end());
for(int i=0;i<10;i++){
cout<<perm[i]<<" ";
}
cout<<"\n";
int z=rand()%10;
cout<<z<<"\n";
minimum_walk(perm,z);
}
return 0;
}*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
8528 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8528 KB |
Output is correct |
| 3 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 4 |
Correct |
1 ms |
8528 KB |
Output is correct |
| 5 |
Correct |
2 ms |
8696 KB |
Output is correct |
| 6 |
Correct |
2 ms |
8784 KB |
Output is correct |
| 7 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 8 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 9 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 10 |
Correct |
1 ms |
8528 KB |
Output is correct |
| 11 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 12 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 13 |
Correct |
1 ms |
8696 KB |
Output is correct |
| 14 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 15 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 16 |
Correct |
2 ms |
8696 KB |
Output is correct |
| 17 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 18 |
Correct |
1 ms |
8528 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
8528 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8528 KB |
Output is correct |
| 3 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 4 |
Correct |
1 ms |
8528 KB |
Output is correct |
| 5 |
Correct |
2 ms |
8696 KB |
Output is correct |
| 6 |
Correct |
2 ms |
8784 KB |
Output is correct |
| 7 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 8 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 9 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 10 |
Correct |
1 ms |
8528 KB |
Output is correct |
| 11 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 12 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 13 |
Correct |
1 ms |
8696 KB |
Output is correct |
| 14 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 15 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 16 |
Correct |
2 ms |
8696 KB |
Output is correct |
| 17 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 18 |
Correct |
1 ms |
8528 KB |
Output is correct |
| 19 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 20 |
Correct |
1 ms |
8528 KB |
Output is correct |
| 21 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 22 |
Correct |
1 ms |
8528 KB |
Output is correct |
| 23 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 24 |
Correct |
2 ms |
8700 KB |
Output is correct |
| 25 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 26 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 27 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 28 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 29 |
Correct |
2 ms |
8528 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
8528 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8528 KB |
Output is correct |
| 3 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 4 |
Correct |
1 ms |
8528 KB |
Output is correct |
| 5 |
Correct |
2 ms |
8696 KB |
Output is correct |
| 6 |
Correct |
2 ms |
8784 KB |
Output is correct |
| 7 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 8 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 9 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 10 |
Correct |
1 ms |
8528 KB |
Output is correct |
| 11 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 12 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 13 |
Correct |
1 ms |
8696 KB |
Output is correct |
| 14 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 15 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 16 |
Correct |
2 ms |
8696 KB |
Output is correct |
| 17 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 18 |
Correct |
1 ms |
8528 KB |
Output is correct |
| 19 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 20 |
Correct |
1 ms |
8528 KB |
Output is correct |
| 21 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 22 |
Correct |
1 ms |
8528 KB |
Output is correct |
| 23 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 24 |
Correct |
2 ms |
8700 KB |
Output is correct |
| 25 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 26 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 27 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 28 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 29 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 30 |
Correct |
136 ms |
28748 KB |
Output is correct |
| 31 |
Correct |
120 ms |
25344 KB |
Output is correct |
| 32 |
Correct |
87 ms |
30796 KB |
Output is correct |
| 33 |
Correct |
87 ms |
27396 KB |
Output is correct |
| 34 |
Correct |
91 ms |
32604 KB |
Output is correct |
| 35 |
Correct |
99 ms |
27208 KB |
Output is correct |
| 36 |
Correct |
98 ms |
29552 KB |
Output is correct |
| 37 |
Correct |
99 ms |
24136 KB |
Output is correct |
| 38 |
Correct |
92 ms |
26696 KB |
Output is correct |
| 39 |
Correct |
96 ms |
25236 KB |
Output is correct |
| 40 |
Correct |
90 ms |
29012 KB |
Output is correct |
| 41 |
Correct |
120 ms |
27208 KB |
Output is correct |
| 42 |
Correct |
109 ms |
26528 KB |
Output is correct |
| 43 |
Correct |
95 ms |
30268 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
12112 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '3306' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
8528 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8528 KB |
Output is correct |
| 3 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 4 |
Correct |
1 ms |
8528 KB |
Output is correct |
| 5 |
Correct |
2 ms |
8696 KB |
Output is correct |
| 6 |
Correct |
2 ms |
8784 KB |
Output is correct |
| 7 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 8 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 9 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 10 |
Correct |
1 ms |
8528 KB |
Output is correct |
| 11 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 12 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 13 |
Correct |
1 ms |
8696 KB |
Output is correct |
| 14 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 15 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 16 |
Correct |
2 ms |
8696 KB |
Output is correct |
| 17 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 18 |
Correct |
1 ms |
8528 KB |
Output is correct |
| 19 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 20 |
Correct |
1 ms |
8528 KB |
Output is correct |
| 21 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 22 |
Correct |
1 ms |
8528 KB |
Output is correct |
| 23 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 24 |
Correct |
2 ms |
8700 KB |
Output is correct |
| 25 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 26 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 27 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 28 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 29 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 30 |
Correct |
136 ms |
28748 KB |
Output is correct |
| 31 |
Correct |
120 ms |
25344 KB |
Output is correct |
| 32 |
Correct |
87 ms |
30796 KB |
Output is correct |
| 33 |
Correct |
87 ms |
27396 KB |
Output is correct |
| 34 |
Correct |
91 ms |
32604 KB |
Output is correct |
| 35 |
Correct |
99 ms |
27208 KB |
Output is correct |
| 36 |
Correct |
98 ms |
29552 KB |
Output is correct |
| 37 |
Correct |
99 ms |
24136 KB |
Output is correct |
| 38 |
Correct |
92 ms |
26696 KB |
Output is correct |
| 39 |
Correct |
96 ms |
25236 KB |
Output is correct |
| 40 |
Correct |
90 ms |
29012 KB |
Output is correct |
| 41 |
Correct |
120 ms |
27208 KB |
Output is correct |
| 42 |
Correct |
109 ms |
26528 KB |
Output is correct |
| 43 |
Correct |
95 ms |
30268 KB |
Output is correct |
| 44 |
Incorrect |
5 ms |
12112 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '3306' |
| 45 |
Halted |
0 ms |
0 KB |
- |
