Submission #1041094

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041094		ReLice	Ancient Books (IOI17_books)	C++17	100 / 100	159 ms	43628 KiB

books

#include "books.h"
#include <bits/stdc++.h>
#define ll int
#define str string
#define ins insert
#define ld long double
#define pb push_back
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define sz size()
#define vll vector<ll>
#define bc back()
#define arr array
#define pll vector<pair<ll,ll>>
using namespace std;		
const ll inf=1e9;
long long minimum_walk(vector<int> p, int s) {
	ll i;
	ll n=p.sz;
	vll l(n,-1);
	vll r(n,-1);
	ll mn=inf,mx=0;
	vll cur;
	long long ans=0;
	
	function<void(ll)> get_cycle = [&](ll v){
		if(cur.sz && v==cur[0])return;
		cur.pb(v);
		get_cycle(p[v]);
	};
	
	for(i=0;i<n;i++){
		ans+=abs(i-p[i]);
		if(l[i]!=-1)continue;
		
		get_cycle(i);
		
		sort(all(cur));
		for(auto j : cur){
			l[j]=cur[0];
			r[j]=cur.bc;
		}
		
		if(cur.sz>1){
			mn=min(mn,cur[0]);
			mx=max(mx,cur.bc);
		}
		cur.clear();
	}
	ll L=s,R=s;
	vll v;
	vector<bool> vis(n,0);
	while(L>mn || R<mx){
		while(v.size()){
			ll x=v.bc;
			v.pob;
			while(L>l[x]){
				L--;
				if(!vis[l[L]]){
					vis[l[L]]=1;
					v.pb(L);
				}
			}
			while(R<r[x]){
				R++;
				if(!vis[l[R]]){
					vis[l[R]]=1;
					v.pb(R);
				}
			}
		}
		
		
		ll nl=L,nr=R;
		ll free=L;
		ll c=0,c2=0;
		
		while(nl>mn){
			if(r[nl]>R) break;
			
			free=min(free,l[nl]);
			if(free==nl) c+=2;
			
			nl--;
		}
		
		free=R;
		while(nr<mx){
			if(l[nr]<L)break;
			
			free=max(free,r[nr]);
			if(free==nr) c2+=2;
			
			nr++;
		}
		
		
		if(l[nr]<L && r[nl]>R){
			if(c<c2){
				ans+=c;
				L=nl;
				v.pb(nl);
			}else{
				ans+=c2;
				R=nr;
				v.pb(nr);
			}
		}else if(r[nl]>R){
			R=nr;
			ans+=c2;
			
			ans+=c;
			L=nl;
			v.pb(nl);
		}else{
			L=nl;
			ans+=c;
			
			ans+=c2;
			R=nr;
			v.pb(nr);
		}
		
	}
	return ans;
}

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