Submission #1066200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066200		alex_2008	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	14 ms	1116 KiB

prison

#include "prison.h"
#include <iostream>
using namespace std;
int get(int x, int ind) {
	while (ind--)
		x /= 3;
	return x % 3;
}
vector<vector<int>> devise_strategy(int N) {
	vector<vector<int>> ans(min(23, N + 1));
	for (auto& it : ans) {
		it.resize(N + 1);
	}
	if (N <= 22) {
		for (int i = 0; i <= N; i++) {
			if (i == 0) ans[i][0] = 0;
			else ans[i][0] = 1;
			for (int j = 1; j <= N; j++) {
				if (i) {
					if (j > i) ans[i][j] = -1;
					else ans[i][j] = -2;
				}
				else ans[i][j] = j;
			}
		}
		return ans;
	}
	else {
		ans[0][0] = 0;
		for (int j = 1; j <= N; j++) {
			ans[0][j] = get(j, 7) + 1;
		}
		for (int i = 1; i <= 21; i++) {
			int ind = (i - 1) / 3;
			int last_dig = (i - 1) % 3;
			if (ind % 2 == 0) ans[i][0] = 1;
			else ans[i][0] = 0;
			for (int j = 1; j <= N; j++) {
				int cur_last_dig = get(j, 7 - ind);
				if (cur_last_dig > last_dig) ans[i][j] = (ans[i][0] == 1) ? -2 : -1;
				else if (cur_last_dig < last_dig) ans[i][j] = (ans[i][0] == 0) ? -2 : -1;
				else {
					if (ind < 6) ans[i][j] = (ind + 1) * 3 + get(j, 6 - ind) + 1;
					else {
						if (get(j, 6 - ind) == 2) ans[i][j] = (ans[i][0] == 1) ? -2 : -1;
						if (get(j, 6 - ind) == 0) ans[i][j] = (ans[i][0] == 0) ? -2 : -1;
						if (get(j, 6 - ind) == 1) ans[i][j] = 22;
					}
				}
			}
		}
		ans[22][0] = 0;
		for (int j = 1; j <= N; j++) {
			if (j % 3 == 0) ans[22][j] = -2;
			else ans[22][j] = -1;
		}
		for (int i = 0; i <= 22; i++) {
			for (int j = 0; j <= N; j++) {
				if (ans[i][j] < 0) ans[i][j] = -3 - ans[i][j];
			}
		}
		return ans;
	}
}

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