Submission #1073986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073986		Gromp15	Prisoner Challenge (IOI22_prison)	C++17	47 / 100	13 ms	1680 KiB

prison

#include <bits/stdc++.h>
#include "prison.h"
#define ll long long
#define ar array
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T> bool ckmin(T &a, const T &b ) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b ) { return a < b ? a = b, 1 : 0; }

std::vector<std::vector<int>> devise_strategy(int N) {
	int req = 0, cur = 1;
	while (cur < N) cur *= 3, req++;
	// req bits
	// [1, N]
	vector<vector<int>> ans(req*4+1, vector<int>(N+1));
	auto split = [&](int x) {
		vector<int> res;
		while (x) {
			res.push_back(x % 3);
			x /= 3;
		}
		while (sz(res) < req) res.emplace_back(0);
		reverse(all(res));
		return res;
	};
	vector<vector<int>> val(N);
	for (int i = 0; i < N; i++) val[i] = split(i);
	for (int i = 0; i <= req*4; i++) {
		if (!i) {
			ans[i][0] = 0;
			for (int j = 1; j <= N; j++) ans[i][j] = (req - 1) * 4 + 1;
		}
		else {
			int bit = req - ((i - 1) / 4) - 1;
			if (i % 4 == 1) {
				// we look 1
				ans[i][0] = 0;
				for (int j = 1; j <= N; j++) {
					ans[i][j] = i + val[j-1][bit] + 1;
				}
			}
			else {
				ans[i][0] = 1;
				int v = i % 4 == 2 ? 0 : i % 4 == 3 ? 1 : 2;
				for (int j = 1; j <= N; j++) {
					if (val[j-1][bit] != v) {
						ans[i][j] = val[j-1][bit] < v ? -2 : -1;
					}
					else {
						ans[i][j] = (i - 1) / 4 == 0 ? 0 : ((i - 1) / 4 - 1) * 4 + 1;
					}
				}
			}
		}
	}
	return ans;
}

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