Submission #1227609

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227609		The_Samurai	Ancient Books (IOI17_books)	C++20	12 / 100	2109 ms	1114112 KiB

books

#include "books.h"
#include "bits/stdc++.h"
using namespace std;

long long minimum_walk(std::vector<int> p, int s) {
	int n = p.size();
	set<pair<vector<int>, int>> vis;
	queue<tuple<vector<int>, int, int>> q;
	vector<int> v(n);
	iota(v.begin(), v.end(), 0);

	auto add = [&](const vector<int> &v, int s, int d) -> void {
		if (vis.count(make_pair(v, s))) return;
		vis.emplace(v, s);
		q.emplace(v, s, d);
	};
	add(v, s, 0);

	while (!q.empty()) {
		auto [v, i, d] = q.front(); q.pop();
		// for (int x: v) cout << x << ' ';
		// cout << endl;
		if (v == p and i == s) return d;
		vector vis(n, false);
		for (int x: v) if (x >= 0) vis[x] = true;
		int have = -1;
		for (int i = 0; i < n; i++) if (!vis[i]) have = i;
		swap(have, v[i]);
		add(v, i, d);
		swap(have, v[i]);
		if (i > 0) add(v, i - 1, d + 1);
		if (i + 1 < n) add(v, i + 1, d + 1);
	}
	assert(false);
	return -1;
}

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