Submission #526864

#	Time	Username	Problem	Language	Result	Execution time	Memory
526864		KoD	Ancient Books (IOI17_books)	C++17	42 / 100	91 ms	16356 KiB

books

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

using std::vector;
using std::array;
using std::pair;
using std::tuple;

using ll = long long;

ll minimum_walk(vector<int> P, int src) {
	{
		int l = 0;
		while (l < src and P[l] == l) {
			l += 1;
		}
		int r = (int)P.size() - 1;
		while (r > src and P[r] == r) {
			r -= 1;
		}
		P.erase(P.begin() + r + 1, P.end());
		P.erase(P.begin(), P.begin() + l);
		for (auto& x : P) {
			x -= l;
		}
		src -= l;
	}
	const int N = P.size();
	assert(N <= 1000);
	vector<int> min(N), max(N);
	vector<char> done(N);
	ll ret = 0;
	for (int i = 0; i < N; ++i) {
		if (!done[i]) {
			vector<int> list;
			for (int j = i; !done[j]; j = P[j]) {
				list.push_back(j);
				ret += std::abs(P[j] - j);
				done[j] = true;
			}
			const int l = *std::min_element(list.begin(), list.end());
			const int r = *std::max_element(list.begin(), list.end());
			for (const int j : list) {
				min[j] = l;
				max[j] = r;
			}
		}
	}
	vector dist(N, vector(N, N + 1));
	std::deque<pair<int, int>> que;
	const auto push0 = [&](const int l, const int r, const int d) {
		if (dist[l][r] > d) {
			dist[l][r] = d;
			que.emplace_front(l, r);
		}
	};
	const auto push1 = [&](const int l, const int r, const int d) {
		if (dist[l][r] > d + 1) {
			dist[l][r] = d + 1;
			que.emplace_back(l, r);
		}
	};
	push0(src, src, 0);
	while (!que.empty()) {
		const auto [l, r] = que.front();
		que.pop_front();
		push0(std::min({l, min[l], min[r]}), std::max({r, max[l], max[r]}), dist[l][r]);
		if (l < r) {
			push0(l + 1, r, dist[l][r]);
			push0(l, r - 1, dist[l][r]);
		}
		if (l > 0) {
			push1(l - 1, r, dist[l][r]);
		}
		if (r + 1 < N) {
			push1(l, r + 1, dist[l][r]);
		}
	}
	return ret + 2 * dist[0][N - 1];
}

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