Submission #299116

#	Time	Username	Problem	Language	Result	Execution time	Memory
299116		keko37	Ancient Books (IOI17_books)	C++14	100 / 100	261 ms	37240 KiB

books

#include<bits/stdc++.h>
#include "books.h"

using namespace std;

typedef long long llint;
typedef vector <int> vi;
typedef pair <int, int> pi;

const int MAXN = 1000005;

llint n, s, sol, cnt;
int curr_lef, curr_rig, lim_lef, lim_rig, edge_lef = -1, edge_rig = -1;
int p[MAXN], ok_pref[MAXN], ok_suf[MAXN];
int bio[MAXN], lo[MAXN], hi[MAXN];

void precompute_ok () {
	for (int i = 0; i < n; i++) {
		if (i > 0) ok_pref[i] |= ok_pref[i - 1];
		if (i != p[i]) ok_pref[i] = 1;
		if (ok_pref[i] == 1 && edge_lef == -1) edge_lef = i;
	}
	for (int i = n-1; i >= 0; i--) {
		if (i + 1 < n) ok_suf[i] |= ok_suf[i + 1];
		if (i != p[i]) ok_suf[i] = 1;
		if (ok_suf[i] == 1 && edge_rig == -1) edge_rig = i;
	}
	while (ok_pref[s] == 0) s++, sol += 2;
	while (ok_suf[s] == 0) s--, sol += 2;	
}

void dfs (int x) {
	bio[x] = cnt;
	lo[cnt] = min(lo[cnt], x);
	hi[cnt] = max(hi[cnt], x);
	if (bio[p[x]] == 0) dfs(p[x]);
}

void find_cycles () {
	for (int i = 0; i < n; i++) {
		if (bio[i] == 0) {
			cnt++;
			lo[cnt] = 1e9; hi[cnt] = -1e9;
			dfs(i);
		}
	}
}

void update () {
	while (curr_lef != lim_lef || curr_rig != lim_rig) {
		if (curr_lef != lim_lef) {
			curr_lef--;
			lim_lef = min(lim_lef, lo[bio[curr_lef]]);
			lim_rig = max(lim_rig, hi[bio[curr_lef]]);
		} else if (curr_rig != lim_rig) {
			curr_rig++;
			lim_lef = min(lim_lef, lo[bio[curr_rig]]);
			lim_rig = max(lim_rig, hi[bio[curr_rig]]);
		}
	}
}

pi cost_lef (int lef, int rig) {
	int res = 0;
	int lim = lef;
	while (1) {
		if (lef == lim) {
			if (lef == edge_lef) return {edge_lef - 1, res};
			lef--; res++;
			if (hi[bio[lef]] > rig) return {lef, res};
			lim = min(lim, lo[bio[lef]]);
		} else {
			lef--;
			if (hi[bio[lef]] > rig) return {lef, res};
			lim = min(lim, lo[bio[lef]]);
		}
	}
}

pi cost_rig (int lef, int rig) {
	int res = 0;
	int lim = rig;
	while (1) {
		if (rig == lim) {
			if (rig == edge_rig) return {edge_rig + 1, res};
			rig++; res++;
			if (lo[bio[rig]] < lef) return {rig, res};
			lim = max(lim, hi[bio[rig]]);
		} else {
			rig++;
			if (lo[bio[rig]] < lef) return {rig, res};
			lim = max(lim, hi[bio[rig]]);
		}
	}
}

void solve () {
	while (1) {
		pi clef = cost_lef(curr_lef, curr_rig);
		pi crig = cost_rig(curr_lef, curr_rig);
		if (clef.first < edge_lef || crig.first > edge_rig) {
			sol += 2 * (clef.second + crig.second);
			break;
		}
		if (clef.second < crig.second) {
			sol += 2 * clef.second;
			lim_lef = clef.first;
			update();
		} else {
			sol += 2 * crig.second;
			lim_rig = crig.first;
			update();
		}
	}
}

llint minimum_walk (vi P, int S) {
	n = P.size(); s = S;
	bool same = 1;
	for (int i = 0; i < n; i++) {
		p[i] = P[i];
		if (p[i] != i) same = 0;
		sol += abs(i - p[i]);
	}
	if (same) return 0;
	precompute_ok();
	find_cycles();
	curr_lef = curr_rig = s;
	lim_lef = lo[bio[s]], lim_rig = hi[bio[s]];
	update();
	solve();
	return sol;
}

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