Submission #33235

#	Time	Username	Problem	Language	Result	Execution time	Memory
33235		model_code	Ancient Books (IOI17_books)	C++11	70 / 100	2000 ms	141384 KiB

books

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

const int INFTY = 10000000;

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].
long long int connect(int l, int r, VI &C, VI &L, VI &R, map<pair<int,int>, int> &Memo) {
	extend(l,r,C,L,R);
	// Memoization lookup: Did we compute it already?
	if(Memo.find({l,r}) != Memo.end()) {
		return Memo[{l,r}];
	}
	// If we have to do something, try going one step to the left or to the right
	// and then take the cheaper of the two.
	int nl, nr; // New interval [nl, nr]
	long long int res = INFTY;
	if(l>0) { // Extend to the left.
		nl = l-1; nr = r;
		extend(nl, nr, C, L, R);
		res = 2+connect(nl, nr, C, L, R, Memo);
	}
	if(r<C.size()-1) {
		nl = l; nr = r+1;
		extend(nl, nr, C, L, R);
		res = min(res,2+connect(nl, nr, C, L, R, Memo));
	}
	Memo[{l,r}] = res;
	return res;
}

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.
		}
	}

	// Use dynamic programming to compute the cost of connecting all cycles.
	map<pair<int,int>, int> Memo;
	Memo[{l,r}] = 0; // If we reach the target we are done.
	return dP+connect(S, S, C, L, R, Memo);
}

Compilation message (stderr)

books.cpp: In function 'long long int connect(int, int, VI&, VI&, VI&, std::map<std::pair<int, int>, int>&)':
books.cpp:54:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(r<C.size()-1) {
      ^

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