Submission #33236

#	Time	Username	Problem	Language	Result	Execution time	Memory
33236		model_code	Ancient Books (IOI17_books)	C++11	100 / 100	273 ms	21560 KiB

books

// Library solution for all S in O(N)
// Score: 100
#include "books.h"
#include <cstdlib>
#include <vector>
#include <map>
#include <iostream>
#include <cassert>

using namespace std;
using VI = vector<int>;

// Compute extend(l,r), initially assuming that the only
// cycles not checked yet are C[l] and C[r].
void extend(int &l, int &r, VI &C, VI &L, VI &R) {
	// [ll, rr] is always the current extension,
	// while only [l,r] was already checked for
	// further overlapping cycles.
	int ll = l, rr = r;
	ll = min(ll,min(L[C[l]], L[C[r]]));
	rr = max(rr,max(R[C[l]], R[C[r]]));

	while(ll<l || r<rr) {
		if(ll<l) {
			l--;
			ll = min(ll,L[C[l]]);
			rr = max(rr,R[C[l]]);
		} else {
			r++;
			ll = min(ll,L[C[r]]);
			rr = max(rr,R[C[r]]);
		}
	}
}

// Compute the remaining cost of non-essentially connecting all the cycles
// if we already connected from S to [l,r] but need to go until we covered
// all of [target_l, target_r].
int connect(int l, int r, int target_l, int target_r, VI &C, VI &L, VI &R) {
	int cost = 0;

	// Repeat as long as [l,r] != [target_l, target_r]
	do {
		extend(l,r,C,L,R);
		// Compute whether there is a next S-including cycle C_l to the left of l 
		// and its reaching cost c_l.
		bool next_l = false; // Does C_l exist?
		int cost_l = 0;
		int l_l=l, r_l=r; // Temporary interval [l_l, r_l].
		while(true) {
			if(l_l<=target_l) break;
			l_l--;
			cost_l += 2;
			extend(l_l,r_l,C,L,R);
			if(r_l>r) { // Detect extension on the other side.
				next_l = true;
				break;
			}
		}
		// Compute whether there is a next S-including cycle C_r to the right of r
		// and its reaching cost c_r.
		bool next_r = false; // Does C_r exist?
		int cost_r = 0;
		int l_r=l, r_r=r; // Temporary interval [l_r, r_r].
		while(true) {
			if(r_r>=target_r) break;
			r_r++;
			cost_r += 2;
			extend(l_r,r_r,C,L,R);
			if(l_r<l) { // Detect extension on the other side.
				next_r = true;
				break;
			}
		}
		// Either there was an S-including cycle on both sides or on none.
		assert(!(next_l ^ next_r)); 
		if(next_l && next_r) { // We can extend on both sides.
			cost += min(cost_l, cost_r); // Take the cheaper of both options.
		} else {
			// If there are no more S-including cycles, then we have to 
			// walk the necessary non-essential steps on both sides.
			cost += cost_l + cost_r;
		}
		// New interval [l,r] = extend(C_l \cup C_r).
		l = min(l_l, l_r);
		r = max(r_l, r_r);
	} while(target_l<l || r<target_r); // As long as Mina needs to explore more.
	return cost;
}

long long minimum_walk(vector<int> order, int S) {
	int N = order.size();
	long long int dP = 0;
	
	// For every slot i, determine its cycle C[i].
	// For every cycle c, determine its interval [L[c], R[c]].
	vector<int> C(N, -1), L(N), R(N);
	int l = S, r = S; // Compute the range that Mina needs to visit.
	int c = 0; // Number of cycles of Pi.
	for(int i=0; i<N; i++) {
		dP += abs(i-order[i]); // Compute d(pi).
		if(C[i] == -1) { // New cycle detected.
			L[c] = i; R[c] = i; // Initialize its leftmost and rightmost slot
			int j = i;
			do { // Loop over the cycle.
				C[j] = c;
				R[c] = max(R[c], j);
				j = order[j];
			} while (i != j);
			if(i != order[i]) {
				// If the cycle is non-trivial, it needs to be part of the
				// range that Mina has to visit.
				l = min(l,L[c]);
				r = max(r,R[c]);
			}
			c++; // Finished processing the cycle containing slot i.
		}
	}
	// Add up the number essential and non-essential steps needed.
	return dP+connect(S, S, l, r, C, L, R);
}

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