Submission #626297

#	Time	Username	Problem	Language	Result	Execution time	Memory
626297		Temmie	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	11 ms	980 KiB

prison

#include <bits/stdc++.h>

std::vector <std::vector <int>> devise_strategy(int n) {
	std::vector <std::vector <int>> ans(21, std::vector <int> (n + 1));
	auto f = [&] (auto&& self, int l, int r, int pl, int pr, int it, int bx, int pbx) -> void {
		if (l > r) {
			return;
		}
		int bag = it & 1;
		ans[it * 3 + bx][0] = bag;
		int bou1 = (l * 2 + r + 1) / 3;
		int bou2 = (r * 2 + l - 1) / 3;
		for (int i = pl; i <= pr; i++) {
			if (i >= l && i <= r) {
				ans[pbx][i] = it * 3 + bx;
			}
			if (i <= l || i >= r) {
				ans[it * 3 + bx][i] = i <= l ? ~bag : ~(1 ^ bag);
			}
		}
		if (l + 1 > r - 1) {
			return;
		}
		if (l + 5 > r - 1) {
			self(self, l + 1, (l + r) >> 1, l, r, it + 1, 1, it * 3 + bx);
			self(self, ((l + r) >> 1) + 1, r - 1, l, r, it + 1, 2, it * 3 + bx);
			return;
		}
		self(self, l + 1, bou1, l, r, it + 1, 1, it * 3 + bx);
		self(self, bou1 + 1, bou2, l, r, it + 1, 2, it * 3 + bx);
		self(self, bou2 + 1, r - 1, l, r, it + 1, 3, it * 3 + bx);
	};
	f(f, 1, n, 1, n, -1, 3, 0);
	return ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 90 / 90