oj.uz

Submission #71535

# Submission time Handle Problem Language Result Execution time Memory
71535 2018-08-25T04:32:32 Z KLPP Ancient Books (IOI17_books) C++14
0 / 100
 2000 ms 1049600 KB 
#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;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2070 ms 870004 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2070 ms 870004 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2070 ms 870004 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory 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 -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2070 ms 870004 KB Time limit exceeded
2 Halted 0 ms 0 KB -