Submission #1032829

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032829		42kangaroo	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	9 ms	1188 KiB

prison

#include "prison.h"

#include <vector>

std::vector<std::vector<int>> devise_strategy(int N) {
	using namespace std;
	vector<vector<int>> strat(23, vector<int>(N + 1, 0));
	vector<int> p3(9);
	p3[0] = 1;
	for (int i = 1; i < 8; ++i) {
		p3[i] = p3[i - 1]*3;
	}
	strat[0][0] = 1;
	for (int i = 1; i <= N; ++i) {
		strat[0][i] = (i / p3[7]) + 1;
	}
	for (int i = 0; i < 6; ++i) {
		strat[1 + 3 * i][0] = strat[2 + 3 * i][0] = strat[3 + 3 * i][0] = i % 2;
		for (int j = 1; j <= N; ++j) {
			if ((j/p3[7 - i]) % 3 == 0) {
				strat[2 + 3*i][j] = strat[3 + 3*i][j] = -1 - i % 2;
				strat[1 + 3 * i][j] = 4 + 3*i + (j/p3[6 - i]) % 3;
			} else if ((j/p3[7 - i]) % 3 == 1){
				strat[3 + 3*i][j] = -1 - i % 2;
				strat[1 + 3*i][j] = -2 + i%2;
				strat[2 + 3 * i][j] = 4 + 3*i + (j/p3[6 - i]) % 3;
			} else {
				strat[2 + 3*i][j] = strat[1 + 3*i][j] = -2 + i % 2;
				strat[3 + 3 * i][j] = 4 + 3*i + (j/p3[6 - i]) % 3;
			}
		}
	}
	strat[19][0] = strat[20][0] = strat[21][0] = 0;
	for (int i = 1; i <= N; ++i) {
		if ((i/p3[1]) % 3 == 0) {
			strat[20][i] = strat[21][i] = -1;
			if (i % 3 == 0) {
				strat[19][i] = -1;
			} else if (i % 3 == 1) {
				strat[19][i] = 22;
			} else {
				strat[19][i] = -2;
			}
		} else if ((i/p3[1]) % 3 == 1){
			strat[21][i] = -1;
			strat[19][i] = -2;
			if (i % 3 == 0) {
				strat[20][i] = -1;
			} else if (i % 3 == 1) {
				strat[20][i] = 22;
			} else {
				strat[20][i] = -2;
			}
		} else {
			strat[20][i] = strat[19][i] = -2;
			if (i % 3 == 0) {
				strat[21][i] = -1;
			} else if (i % 3 == 1) {
				strat[21][i] = 22;
			} else {
				strat[21][i] = -2;
			}
		}
	}
	strat[22][0] = 1;
	for (int i = 1; i <= N; ++i) {
		strat[22][i] = -1 - ((i % 3) == 0);
	}
	return strat;
}

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