Submission #364733

#	Time	Username	Problem	Language	Result	Execution time	Memory
364733		rqi	Ancient Books (IOI17_books)	C++14	50 / 100	1617 ms	1048580 KiB

books

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

typedef vector<int> vi;
typedef long long ll;

#define sz(x) (int)(x).size()
#define pb push_back
#define bk back()

const int MOD = 1e9+7;

const int mx = 1000005;
vi p;
int s;
int cycL[mx]; //leftmost of a cycle
int cycR[mx]; //rightmost of a cycle

void popLRSingles(){
	int L = 0;
	for(int i = 0; i < s; i++){
		if(p[i] == i){
			L = i+1;
		}
		else{
			break;
		}
	}

	vi newp;
	for(int i = L; i < sz(p); i++){
		newp.pb(p[i]);
	}

	p = newp;
	s = s-L;

	while(true){
		if(sz(p)-1 == s) break;
		if(p[sz(p)-1] == sz(p)-1){
			p.pop_back();
		}
		else{
			break;
		}
	}
}

int curL, curR;

vi Lfrees, Rfrees;

void getFrees(){
	while(true){
		bool updated = false;

		while(sz(Lfrees)){
			int node = Lfrees.bk;
			if(node < curL) break;
			updated = true;
			Lfrees.pop_back();
			curL = min(curL, cycL[node]);
			curR = max(curR, cycR[node]);
		}

		while(sz(Rfrees)){
			int node = Rfrees.bk;
			if(node > curR) break;
			updated = true;
			Rfrees.pop_back();
			curL = min(curL, cycL[node]);
			curR = max(curR, cycR[node]);
		}

		if(!updated) break;
	}
}

long long minimum_walk(vi _p, int _s) {
	p = _p;
	s = _s;
	popLRSingles();
	int n = sz(p);

	for(int i = 0; i < n; i++){
		cycL[i] = MOD;
		cycR[i] = -1;
	}

	for(int i = 0; i < n; i++){
		if(cycR[i] == -1){
			int curnode = i;

			vi cycle_nodes;
			while(true){
				cycle_nodes.pb(curnode);
				curnode = p[curnode];
				if(curnode == i) break;
			}

			for(auto u: cycle_nodes){
				cycL[i] = min(cycL[i], u);
				cycR[i] = max(cycR[i], u);
			}

			for(auto u: cycle_nodes){
				cycL[u] = cycL[i];
				cycR[u] = cycR[i];
			}
		}
	}

	ll ans = 0;

	for(int i = 0; i < n; i++){
		ans+=abs(p[i]-i);
	}



	curL = s;
	curR = s;

	for(int i = 0; i <= s; i++){
		Lfrees.pb(i);
	}
	for(int i = n-1; i >= s; i--){
		Rfrees.pb(i);
	}
	getFrees();

	while(curL > 0 || curR < n-1){
		int prev_curL = curL;
		int prev_curR = curR;

		ll L_cost = 0;
		ll R_cost = 0;
		bool non_boost = false;

		for(int i = curL-1; i >= 0; i--){
			if(i+1 == curL){
				L_cost+=2;
				curL--;
			}

			curL = min(curL, cycL[i]);
			if(cycR[i] > prev_curR){
				//found non boost
				non_boost = true;
				break;
			}
		}

		for(int i = curR+1; i < n; i++){
			if(i-1 == curR){
				R_cost+=2;
				curR++;
			}

			curR = max(curR, cycR[i]);
			if(cycL[i] < prev_curL){
				non_boost = true;
				break;
			}
		}

		if(!non_boost){
			ans+=L_cost+R_cost;
		}
		else{
			ans+=min(L_cost, R_cost);
		}

		getFrees();
	}

	return ans;
}

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