Submission #51837

#	Time	Username	Problem	Language	Result	Execution time	Memory
51837		aome	Ancient Books (IOI17_books)	C++17	100 / 100	253 ms	167404 KiB

books

#include <bits/stdc++.h>
#include "books.h"
 
using namespace std;
 
const int N = 1000005;
 
long long minimum_walk(vector<int> p, int s) {
	int n = p.size();
	long long res = 0;
	for (int i = 0; i < n; ++i) res += abs(i - p[i]);
	int ml = n - 1, mr = 0;
	for (int i = 0; i < n; ++i) {
		if (i != p[i]) ml = min(ml, i), mr = max(mr, i);
	}
	int cl = s, cr = s;
	queue<int> qu; qu.push(s);
	while (1) {
		while (qu.size()) {
			int u = qu.front(); qu.pop();
			while (cl > p[u]) {
				cl--, qu.push(cl);
			}
			while (cr < p[u]) {
				cr++, qu.push(cr);
			}
		}
		int l = cl, r = cr;
		int dl = 0, dr = 0;
		bool fl = 0, fr = 0;
		queue<int> ql, qr;
		while (1) {
			if (l <= ml) break;
			l--, dl++, ql.push(l);
			while (ql.size()) {
				int u = ql.front(); ql.pop();
				while (l > p[u]) {
					l--, ql.push(l);
				}
				if (p[u] > s) fl = 1;
			}
			if (fl) break; 
		}
		while (1) {
			if (r >= mr) break;
			r++, dr++, qr.push(r);
			while (qr.size()) {
				int u = qr.front(); qr.pop();
				while (r < p[u]) {
					r++, qr.push(r);
				}
				if (p[u] < s) fr = 1;
			}
			if (fr) break;
		}
		if (fl && fr) {
			res += 2 * min(dl, dr);
			while (cl > l) qu.push(--cl);
			while (cr < r) qu.push(++cr);
		}
		else {
			res += 2 * (dl + dr); break;
		}
	}
	return res;
}

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