Submission #568987

#	Time	Username	Problem	Language	Result	Execution time	Memory
568987		Siffer	Ancient Books (IOI17_books)	C++14	100 / 100	210 ms	26700 KiB

books

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

#define ll long long
#define F first
#define S second
#define vi vector<int>
#define ii pair<int, int>

ii explore(int f1, int f2, int t2, int t1, vi &mi, vi &ma, vi &c) {
	int f3 = f1;
	int t3 = t1;
	for(int i = f1; i <= t1; i++) {
		if(i == f2) {
			i = t2+1;
			if(i > t1) continue;
		}
		f3 = min(f3, mi[c[i]]);
		t3 = max(t3, ma[c[i]]);
	}
	if(f3 == f1 && t3 == t1) return {f1, t1};
	return explore(f3, f1, t1, t3, mi, ma, c);
}

ll minimum_walk(vi p, int s) {
	int n = p.size();
	ll res = 0;
	vi c(n,-1), mi(n, n), ma(n, 0);
	for(int i = 0; i < n; i++) {
		if(c[i] == -1) {
			int k = p[i];
			c[i] = i;
			mi[i] = i;
			ma[i] = i;
			res += p[i] - i;
			while(k != i) {
				c[k] = i;
				res += abs(p[k]-k);
				mi[i] = min(mi[i], k);
				ma[i] = max(ma[i], k);
				k = p[k];
			}
		}
	}
	ii lr = explore(s,-1,-1,s,mi,ma,c);
	int l = lr.F; int r = lr.S;
	ll lc = 0; ll rc = 0;
	while(l || r < n-1) {
		bool b = 1;
		if(l) {
			lc += 2;
			lr = explore(l-1,l,r,r,mi,ma,c);
			l = lr.F;
			if(lr.S > r) {
				r = lr.S;
				b = 0;
				res += lc;
				rc = 0;
				lc = 0;
			}
		}
		if(r < n-1 && b) {
			rc += 2;
			lr = explore(l,l,r,r+1,mi,ma,c);
			r = lr.S;
			if(lr.F < l) {
				l = lr.F;
				res += rc;
				rc = 0;
				lc = 0;
			}
		}
	}
	for(int i = 0; i < s; i++) {
		if(p[i] == i) res -= 2;
		else break;
	}
	for(int i = n-1; i > s; i--) {
		if(p[i] == i) res -= 2;
		else break;
	}
	return res + lc + rc;
}

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