Submission #776208

#	Time	Username	Problem	Language	Result	Execution time	Memory
776208		SanguineChameleon	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	10 ms	1400 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;

const int M = 20;

vector<vector<int>> devise_strategy(int N) {
	vector<pair<int, int>> dp(M + 1);
	dp[0] = make_pair(2, -1);
	for (int i = 1; i <= M; i++) {
		for (int j = 0; j < i; j++) {
			dp[i] = max(dp[i], make_pair(dp[j].first * (i - j) + 2, i - j));
		}
	}
	vector<int> split;
	split.push_back(1);
	int rem = M;
	while (rem > 0) {
		split.push_back(dp[rem].second);
		rem -= dp[rem].second;
	}
	vector<vector<int>> repr(N + 1);
	for (int i = 1; i <= N; i++) {
		int pos = i - 1;
		int len = dp[M].first;
		int off = 1;
		for (int j = 1; ; j++) {
			if (pos == 0) {
				repr[i].push_back(0);
				break;
			}
			if (pos == len - 1) {
				repr[i].push_back(M + 1);
				break;
			}
			pos--;
			len = (len - 2) / split[j];
			repr[i].push_back(off + pos / len);
			pos %= len;
			off += split[j];
		}
	}
	vector<vector<int>> res(M + 1, vector<int>(N + 1, 0));
	int off = 0;
	for (int i = 0; i < (int)split.size(); i++) {
		for (int j = off; j < off + split[i]; j++) {
			res[j][0] = (i & 1);
			for (int k = 1; k <= N; k++) {
				int prv = (i ? repr[k][i - 1] : 0);
				if (prv != j) {
					res[j][k] = (-1) - ((i & 1) ^ (prv > j));
					continue;
				}
				int cur = repr[k][i];
				if (cur == 0) {
					res[j][k] = (-1) - (i & 1);
				}
				else if (cur == M + 1) {
					res[j][k] = (-1) - ((i & 1) ^ 1);
				}
				else {
					res[j][k] = cur;
				}
			}
		}
		off += split[i];
	}
	return res;
}

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