#include "books.h"
#include<iostream>
#include<vector>
#include<queue>
#include<map>
using namespace std;
typedef long long lld;
typedef pair<int,int> state;
typedef std::map<state,lld>::iterator mi;
int arr[1000000];
int n;
int maxa,maxb;
map<state,lld>DP;
lld computevalue(int i, int j){
//cout<<i<<" "<<j<<endl;
if(i== maxa && j==maxb)return 0;
int pntl=i-1;
int cntl=0;
bool b=true;
while(pntl>=maxa && b){//cout<<pntl<<endl;
int start=pntl;
int end=pntl;
int ps=start;
int pe=end;
while(pe<=end && pe<i){
while(ps>=start){
start=min(start,arr[ps]);
end=max(end,arr[ps]);
ps--;
}
start=min(start,arr[pe]);
end=max(end,arr[pe]);
pe++;
}
if(start>=i){
b=false;
}cntl++;
pntl=start;
pntl--;
}
int pntr=j+1;
int cntr=0;
b=true;
//cout<<endl;
while(pntr<=maxb && b){
int start=pntr;
int end=pntr;
int ps=start;
int pe=end;
while(ps>=start && ps>j){
while(pe<=end){//cout<<pe<<" "<<ps<<endl;
start=min(start,arr[ps]);
end=max(end,arr[ps]);
pe++;
}
start=min(start,arr[pe]);
end=max(end,arr[pe]);
ps--;
}
if(end<=j){
b=false;
}cntr++;
pntr=end;
pntr++;
}
//cout<<cntl<<" "<<cntr<<endl;
int start,end;
start=i;
end=j;
if(cntl<cntr){
int extra=0;
while(cntl-- && start>maxa){
extra+=2;
start--;
int pe=end;
int ps=start;
while(pe<=end){
while(ps>=start){
start=min(start,arr[ps]);
end=max(end,arr[ps]);
ps--;
}
start=min(start,arr[pe]);
end=max(end,arr[pe]);
pe++;
}
}
return computevalue(start,end)+extra;
}
int extra=0;
while(cntr-- && end<maxb){
extra+=2;
end++;
int pe=end;
int ps=start;
while(pe<=end){
while(ps>=start){
start=min(start,arr[ps]);
end=max(end,arr[ps]);
ps--;
}
start=min(start,arr[pe]);
end=max(end,arr[pe]);
pe++;
}
}
return computevalue(start,end)+extra;
}
lld abs(lld x){
if(x>0)return x;
return -x;
}
long long minimum_walk(std::vector<int> p, int s) {
n=p.size();
for(int i=0;i<n;i++){
arr[i]=p[i];
}
maxa=n;
for(int i=0;i<n;i++){
if(p[i]!=i){
maxa=i;
i=n;
}
}
maxb=-1;
for(int i=n-1;i>-1;i--){
if(p[i]!=i){
maxb=i;
i=-1;
}
}
//cout<<maxa<<" "<<maxb<<endl;
lld ans=0;
for(int i=0;i<n;i++)ans+=abs(p[i]-i);
//cout<<ans<<endl;
int start=s;
int end=s;
int ps=start;
int pe=end;
while(pe<=end){
while(ps>=start){
start=min(start,arr[ps]);
end=max(end,arr[ps]);
ps--;
}
start=min(start,arr[pe]);
end=max(end,arr[pe]);
pe++;
}//cout<<ans<<endl;
ans+=computevalue(start,end);
return ans;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2070 ms |
870004 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2070 ms |
870004 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2070 ms |
870004 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1627 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2070 ms |
870004 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
