Submission #68031

#	Time	Username	Problem	Language	Result	Execution time	Memory
68031		KLPP	Ancient Books (IOI17_books)	C++14	70 / 100	2053 ms	104732 KiB

books

#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 && maxb<=j)return 0;
	mi it=DP.find(state(i,j));
	if(it!=DP.end())return it->second;
	int start=i;
	int end=j;
	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++;
	}
	lld ans=1000000000000000000;
	if(start<=maxa && maxb<=end){
		DP[state(i,j)]=0;
		return 0;
	}
	if(start>maxa){
		ans=min(ans,computevalue(start-1,end)+2);
	}
	if(end<maxb){
		ans=min(ans,computevalue(start,end+1)+2);
	}
	DP[state(i,j)]=ans;
	return ans;
}
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;
	ans+=computevalue(s,s);
	return ans;
}

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 28 / 28
• Subtask 4: 20 / 20
• Subtask 5: 0 / 30