Submission #1147687

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147687		gyg	Ancient Books (IOI17_books)	C++20	0 / 100	0 ms	324 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define sig signed 
#define int long long
#define arr array
#define vec vector 
const int N = 1e6 + 5;

int n, st;
arr<int, N> out;

arr<bool, N> vs;
vec<int> cyc;
void dfs(int u) {
	vs[u] = true, cyc.push_back(u);
	if (vs[out[u]]) return;
	dfs(out[u]);
}

int cmp() {
	int ans = 0, mx = -1;
	for (int u = 1; u <= n; u++) {
		if (vs[u]) continue;
		mx = max(mx, u);
		dfs(u);

		for (int i = 0; i < cyc.size(); i++) {
			int j = (i + 1) % cyc.size();
			ans += abs(cyc[i] - cyc[j]);
		}
		cyc.clear();
		// cout << u << ": " << ans << '\n';
	}
	assert(mx != -1);
	ans += 2 * (mx - 1);
	return ans;
}

int minimum_walk(vec<sig> _out, sig _st) {
	n = _out.size(), st = _st + 1;
	for (int i = 1; i <= n; i++) out[i] = _out[i - 1] + 1;

	int ans = cmp();
	return ans;
}

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