Submission #1105070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105070		alexander707070	Ancient Books (IOI17_books)	C++14	50 / 100	124 ms	29436 KiB

books

#include<bits/stdc++.h>
#define MAXN 1000007
using namespace std;
 
int n,s,p[MAXN],fr,last,mins,maxs,pref[MAXN],curr,A,B;
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<=A and r>=B)return 0;
	
	if(vis[l][r])return dp[l][r];
	vis[l][r]=true;
	dp[l][r]=2*n;
 
	if(l>A){
		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<B){
		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(p[i]!=i)B=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(p[i]!=i)A=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){
      int from=s,to=s,ll=s,rr=s;
		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++;
			}
		}
      ans+=ff(from,to);
    }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;
}*/

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