Submission #627963

#	Time	Username	Problem	Language	Result	Execution time	Memory
627963		jhwest2	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	12 ms	1180 KiB

prison

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

const int X[9] = { 3, 3, 3, 3, 3, 2, 2, 1 };
const int Y[9] = { 0, 1, 4, 7, 10, 13, 16, 18, 20 };
int a[10][5050];

void init(int l, int r, int k) {
	a[k][l] = -1;
	a[k][r] = -2;
	if (r - l <= 1) return;
	++l; --r;

	int d = (r - l + X[k]) / X[k];
	int c = 0;
	for (; l + d - 1 <= r; l += d) {
		for (int j = l; j < l + d; j++) {
			a[k][j] = c;
		}
		++c;
		init(l, l + d - 1, k + 1);
	}
	if (l <= r) {
		for (int j = l; j <= r; j++) {
			a[k][j] = c;
		}
		++c;
		init(l, r, k + 1);
	}
}
vector<vector<int>> devise_strategy(int n) {
	init(1, 5000, 0);
	vector<vector<int>> ans(21, vector<int>(n + 1));
	for (int i = 0; i < 21; i++) {
		int m = 0;
		for (int j = 8; j >= 0; j--) {
			if (i >= Y[j]) {
				m = j; break;
			}
		}
		ans[i][0] = m & 1;

		for (int j = 1; j <= n; j++) {
			if (m != 0) {
				if (a[m - 1][j] == -1) {
					ans[i][j] = -1 - ans[i][0];
					continue;
				}
				if (a[m - 1][j] == -2) {
					ans[i][j] = -2 + ans[i][0];
					continue;
				}
				if (i - Y[m] != a[m - 1][j]) {
					if (i - Y[m] < a[m - 1][j]) ans[i][j] = -2 + ans[i][0];
					else ans[i][j] = -1 - ans[i][0];
					continue;
				}
			}
			if (a[m][j] == -1) ans[i][j] = -1 - ans[i][0];
			else if (a[m][j] == -2) ans[i][j] = -2 + ans[i][0];
			else if (i < 20) {
				ans[i][j] = Y[m + 1] + a[m][j];
			}
		}
	}
	return ans;
}

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