Submission #526855

#	Time	Username	Problem	Language	Result	Execution time	Memory
526855		KoD	Ancient Books (IOI17_books)	C++17	50 / 100	108 ms	18892 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) {
	assert(src == 0);
	if (std::is_sorted(P.begin(), P.end())) {
		return 0;
	}
	while (P.back() == (int)P.size() - 1) {
		P.pop_back();
	}
	const int N = P.size();
	vector<int> coeff(N);
	ll ret = 0;
	for (int i = 0; i < N; ++i) {
		const int x = std::min(i, P[i]);
		const int y = std::max(i, P[i]);
		coeff[x] += 1;
		coeff[y] -= 1;
		ret += y - x;
	}
	for (int i = 0; i < N - 1; ++i) {
		if (coeff[i] == 0) {
			ret += 2;
		}
		coeff[i + 1] += coeff[i];
	}
	return ret;
}

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