Submission #51568

#	Time	Username	Problem	Language	Result	Execution time	Memory
51568		aome	Ancient Books (IOI17_books)	C++17	50 / 100	238 ms	13516 KiB

books

#include <bits/stdc++.h>
#include "books.h"
 
using namespace std;
 
const int N = 1000005;
 
bool visit[N];
 
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 l, r;
	l = r = s;

	queue<int> qu;
	qu.push(s), visit[s] = 1;

	while (1) {
		while (qu.size()) {
			int u = qu.front(); qu.pop();

			while (l > p[u]) {
				l--, visit[l] = 1, qu.push(l);
			}
			while (r < p[u]) {
				r++, visit[r] = 1, qu.push(r);
			}
		}

		int tl = l, tr = r;
		int cnt = 0;
		bool found = 0;
		while (1) {
			++cnt;

			l--;
			if (l >= 0 && p[l] != l) {
				found = 1, qu.push(l), r = tr; break;
			}
			r++;
			if (r < n && p[r] != r) {
				found = 1, qu.push(r), l = tl; break;
			}

			if (l < 0 && r >= n) break;
		}

		if (!found) break;
		res += cnt * 2;
	}

	return res;
}

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