Submission #1227627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227627		The_Samurai	Ancient Books (IOI17_books)	C++20	22 / 100	2093 ms	16324 KiB

books

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

struct dsu {
	vector<vector<int>> childs;
	vector<int> par;

	void init(int n) {
		childs.assign(n, {});
		par.assign(n, 0);
		for (int i = 0; i < n; i++) par[i] = i, childs[i].emplace_back(i);
	}

	int get(int a) { return par[a]; }

	void merge(int a, int b) {
		if (par[a] == par[b]) return;
		a = par[a]; b = par[b];
		if (childs[a].size() < childs[b].size()) swap(a, b);
		for (int x: childs[b]) {
			par[x] = a;
			childs[a].emplace_back(x);
		}
		childs[b].clear();
	}
};

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);
	int until = n - 1;
	while (until >= 0 and p[until] == until) until--;
	int exp = 0;
	for (int i = 0; i <= until; i++) exp += abs(p[i] - i);
	if (until < 0) return 0;
	exp -= 2;
	vector added(n, false);
	for (int i = 0; i <= until; i++) {
		exp += 2;
		int mx = i;
		added[i] = true;
		vector<int> vec = {i};
		// cout << i << endl;
		for (int j = 0; j < vec.size(); j++) {
			mx = max(mx, vec[j]);
			for (int k = vec[j] + 1; k <= p[vec[j]]; k++) {
				if (added[k]) continue;
				added[k] = true;
				vec.emplace_back(k);
			}
		}
		i = mx;
	}
	return exp;
	// dsu ds; ds.init(n + 1);
	// for (int i = 0; i < n; i++) ds.merge(i, p[i]);
	// int cnt = 0;
	// for (int i = 0; i < n; i++) if (ds.get(i) == i) cnt += ds.childs[i].size() > 1;
	// if (cnt > 1) {
	// 	cout << "shit" << endl;
	// }
	

	auto add = [&](const vector<int> &v, int i, int d) -> void {
		if (vis.count(make_pair(v, i))) return;
		vis.emplace(v, i);
		q.emplace(v, i, 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) {
			assert(d == exp);
			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: 10 / 10
• Subtask 3: 0 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30