Submission #560321

#	Time	Username	Problem	Language	Result	Execution time	Memory
560321		jamezzz	Ancient Books (IOI17_books)	C++17	50 / 100	2087 ms	26572 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;

#define maxn 1000005

int n,cl[maxn],cr[maxn],c[maxn];

void extend(int &l,int &r){
	//printf("extend: %d %d\n",l,r);
	int farl=min(cl[c[l]],cl[c[r]]);
	int farr=max(cr[c[l]],cr[c[r]]);
	while(true){
		if(farl<l){
			--l;
			farl=min(farl,cl[c[l]]);
			farr=max(farr,cr[c[l]]);
		}
		else if(r<farr){
			++r;
			farl=min(farl,cl[c[r]]);
			farr=max(farr,cr[c[r]]);
		}
		else break;
	}
	//printf("res: %d %d\n",l,r);
}

ll minimum_walk(vector<int> p,int s){
	n=p.size();
	int lbound=s,rbound=s;
	ll ans=0;int cnt=1;
	for(int i=0;i<n;++i){
		if(c[i]!=0)continue;
		int x=i;
		cl[cnt]=cr[cnt]=i;
		while(true){
			c[x]=cnt;
			cl[cnt]=min(cl[cnt],x);
			cr[cnt]=max(cr[cnt],x);
			ans+=abs(x-p[x]);
			x=p[x];
			if(x==i)break;
		}
		if(x!=p[x]){
			lbound=min(lbound,cl[cnt]);
			rbound=max(rbound,cr[cnt]);
		}
		++cnt;
	}
	
	int l=s,r=s;
	while(l!=lbound||r!=rbound){
		//printf("%d %d\n",l,r);
		extend(l,r);
		bool can=false;
		int newl=n,newr=0;
		
		int tmpl=l,tmpr=r;
		int lcost=0;
		while(true){
			if(tmpl<=lbound)break;//done
			--tmpl;lcost+=2;
			extend(tmpl,tmpr);
			if(tmpr>r){
				can=true;
				break;
			}
		}
		tmpl=l,tmpr=r;
		int rcost=0;
		while(true){
			if(tmpr>=rbound)break;//done
			++tmpr;rcost+=2;
			extend(tmpl,tmpr);
			if(tmpl<l){
				can=true;
				break;
			}
		}
		
		if(can)ans+=min(lcost,rcost);
		else ans+=lcost+rcost;
		
		l=tmpl,r=tmpr;
	}
	return ans;
}

Compilation message (stderr)

books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:60:7: warning: unused variable 'newl' [-Wunused-variable]
   60 |   int newl=n,newr=0;
      |       ^~~~
books.cpp:60:14: warning: unused variable 'newr' [-Wunused-variable]
   60 |   int newl=n,newr=0;
      |              ^~~~

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