Submission #51557

#	Time	Username	Problem	Language	Result	Execution time	Memory
51557		aome	Ancient Books (IOI17_books)	C++17	50 / 100	312 ms	13628 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) {
	long long optsum = 1e18;

	for (int l = 0; l <= s; ++l) {

		int n = p.size();
		int cur = l, lim = l;
		long long sum = 0;

		for (int i = 0; i < n; ++i) {
			sum += abs(p[i] - i);
			visit[i] = 0;
		}

		for (int i = l; i < n; ++i) {
			if (i != p[i]) lim = i;
		}

		while (1) {
			queue<int> qu;
			visit[cur] = 1, qu.push(cur);
	 
			while (qu.size()) {
				int u = qu.front(); qu.pop();
				while (cur < p[u]) {
					cur++, visit[cur] = 1, qu.push(cur);
				}
			}
	 
			if (cur == lim) break;
			sum += 2, cur++;
		}

		queue<int> qu;
		for (int i = 0; i < n; ++i) {
			if (visit[i]) qu.push(i);
		}

		while (qu.size()) {
			int u = qu.front(); qu.pop();
			if (!visit[p[u]]) {
				visit[p[u]] = 1, qu.push(p[u]);
			}
		}

		bool fail = 0;
		for (int i = 0; i < n; ++i) fail |= !visit[i] && i != p[i];

		if (!fail) optsum = min(optsum, sum);
	}

	return optsum;
}

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