Submission #797526

#	Time	Username	Problem	Language	Result	Execution time	Memory
797526		alvingogo	Ancient Books (IOI17_books)	C++14	50 / 100	200 ms	33780 KiB

books

#include "books.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

typedef long long ll;
ll minimum_walk(vector<int> p, int s) {
	ll ans=0;
	int n=p.size();
	vector<int> bo(n,-1),bo2(n,-1),k(n),pre(n);
	vector<pair<int,int> > d(n);
	for(int i=0;i<n;i++){
		if(bo[i]==-1){
			pre[i]++;
			int cnt=0;
			int f=0;
			for(int x=i;bo[x]==-1;x=p[x]){
				bo[x]=i;
				cnt++;
				f=max(f,x);
			}
			if(cnt>=2){
				k[i]=1;
			}
			pre[f]--;
			for(int x=i;bo2[x]==-1;x=p[x]){
				bo2[x]=i;
				d[x]={i,f};
			}
		}
		ans+=abs(i-p[i]);
	}
	int l=d[s].fs,r=d[s].sc,nl=s,nr=s;
	while(nl>l || nr<r){
		if(nl>l){
			nl--;
			l=min(l,d[nl].fs);
			r=max(r,d[nl].sc);
		}
		else if(nr<r){
			nr++;
			l=min(l,d[nr].fs);
			r=max(r,d[nr].sc);
		}
	}
	for(int i=1;i<n;i++){
		pre[i]+=pre[i-1];
	}
	int g=0;
	k[bo[s]]=1;
	vector<pair<int,int> > e;
	for(int i=0;i<n;i++){
		if(pre[i]){

		}
		else{
			if(g<=nl && i>=nr){
				while(nl!=g && nr!=i){
					int pl=l,pr=r;
					int c1=0;
					while(1){
						c1++;
						int dl=nl-1,dr=nr;
						while(nl>dl || nr<dr){
							if(nl>dl){
								nl--;
								dl=min(dl,d[nl].fs);
								dr=max(dr,d[nl].sc);
							}
							else if(nr<dr){
								nr++;
								dl=min(dl,d[nr].fs);
								dr=max(dr,d[nr].sc);
							}
						}
						if(nr!=pr){
							pl=nl;
							pr=nr;
							break;
						}
					}
					int c2=0;
					while(1){
						c2++;
						int dl=nl,dr=nr+1;
						while(nl>dl || nr<dr){
							if(nl>dl){
								nl--;
								dl=min(dl,d[nl].fs);
								dr=max(dr,d[nl].sc);
							}
							else if(nr<dr){
								nr++;
								dl=min(dl,d[nr].fs);
								dr=max(dr,d[nr].sc);
							}
						}
						if(nl==pl){
							break;
						}
					}
					ans+=2*min(c1,c2);
				}
			}
			if(i!=g || i==s){
				e.push_back({g,i});
			}
			g=i+1;
		}
	}
	int nw=e[0].fs;
	for(auto h:e){
		ans+=2*(h.fs-nw);
		nw=h.sc;
	}
	return ans;
}

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