Submission #1037387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037387		42kangaroo	Prisoner Challenge (IOI22_prison)	C++17	0 / 100	3 ms	604 KiB

prison

#include "prison.h"

#include "bits/stdc++.h"

std::vector<std::vector<int>> devise_strategy(int N) {
	using namespace std;
	vector<vector<int>> strat(21, vector<int>(N + 1, 0));

	set<int> in;
	vector<int> sis{1700, 566, 188, 62, 20, 6};
	strat[0][0] = 1;
	strat[0][1] = -2;
	in.insert(1);
	in.insert(5102);
	for (int i = 2; i <= N; ++i) {
		strat[0][i] = 1 + (i - 2)/(sis[0]);
	}
	for (int i = 0; i < 5; ++i) {
		strat[1 + 3*i][0] = strat[2 + 3*i][0] = strat[3 + 3*i][0] = i%2;
		vector<int> nex;
		for (int j = 1; j <= N; ++j) {
			auto ne = in.lower_bound(j);
			if (*ne == j) {
				strat[1 + 3*i][j] = strat[2 + 3*i][j] = strat[3 + 3*i][j] = (strat[3*i][j] == -1 ? -2: -1);
			} else {
				auto be = prev(ne);
				if ((j - *be - 1)/sis[i] == 0) {
					strat[2 + 3*i][j] = strat[3 + 3*i][j] = -1 - i%2;
					if (j == *be + 1) {
						nex.push_back(j);
						strat[1 + 3*i][j] = -1 - i%2;
					} else if ((j - *be)/sis[i] == 1) {
						nex.push_back(j);
						strat[1 + 3*i][j] = -2 + i%2;
					} else {
						strat[1 + 3*i][j] = 4 + 3*i + (j - *be - 2)/sis[i + 1];
					}
				} else if ((j - *be - 1)/sis[i] == 1) {
					strat[3 + 3*i][j] = -1 - i%2;
					strat[1 + 3*i][j] = -2 + i%2;
					if (j == *be + sis[i] + 1) {
						nex.push_back(j);
						strat[2 + 3*i][j] = -1 - i%2;
					} else if ((j - *be)/sis[i] == 2) {
						nex.push_back(j);
						strat[2 + 3*i][j] = -2 + i%2;
					} else {
						strat[2 + 3*i][j] = 4 + 3*i + (j - *be - 2 - sis[i])/sis[i + 1];
					}
				} else {
					strat[2 + 3*i][j] = strat[1 + 3*i][j] = -2 + i%2;
					if (j == *be + 1 + 2*sis[i]) {
						nex.push_back(j);
						strat[3 + 3*i][j] = -1 - i%2;
					} else if ((j - *be)/sis[i] == 3) {
						nex.push_back(j);
						strat[3 + 3*i][j] = -2 + i%2;
					} else {
						strat[3 + 3*i][j] = 4 + 3*i + (j - *be - 2 - 2*sis[i])/sis[i + 1];
					}
				}
			}
		}
		in.insert(nex.begin(), nex.end());
	}
	strat[16][0] = strat[17][0] = strat[18][0] = 1;
	vector<int> nex;
	for (int j = 1; j <= N; ++j) {
		auto ne = in.lower_bound(j);
		if (*ne == j) {
			strat[16][j] = strat[17][j] = strat[18][j] = (strat[15][j] == -1 ? -2: -1);
		} else {
			auto be = prev(ne);
			if ((j - *be - 1)/6 == 0) {
				strat[17][j] = strat[18][j] = -2;
				if (j == *be + 1) {
					nex.push_back(j);
					strat[16][j] = -2;
				} else if ((j - *be)/6 == 1) {
					nex.push_back(j);
					strat[16][j] = -1;
				} else {
					strat[16][j] = 19 + (j - *be - 2)/2;
				}
			} else if ((j - *be - 1)/6 == 1) {
				strat[18][j] = -2;
				strat[16][j] = -1;
				if (j == *be + 7) {
					nex.push_back(j);
					strat[17][j] = -2;
				} else if ((j - *be)/6 == 2) {
					nex.push_back(j);
					strat[17][j] = -1;
				} else {
					strat[17][j] = 19 + (j - *be - 8)/2;
				}
			} else {
				strat[17][j] = strat[16][j] = -1;
				if (j == *be + 13) {
					nex.push_back(j);
					strat[18][j] = -2;
				} else if ((j - *be)/6 == 3) {
					nex.push_back(j);
					strat[18][j] = -1;
				} else {
					strat[18][j] = 19 + (j - *be - 14)/2;
				}
			}
		}
	}
	in.insert(nex.begin(), nex.end());
	strat[19][0] = strat[20][0] = 0;
	for (int j = 1; j <= N; ++j) {
		auto ne = in.lower_bound(j);
		if (*ne == j) {
			strat[19][j] = strat[20][j] = (strat[18][j] == -1 ? -2: -1);
		} else {
			auto be = prev(ne);
			if ((j - *be - 1)/2 == 0) {
				strat[20][j] = -1;
				strat[19][j] = -1 - (j - *be - 3 == 0);
			} else {
				strat[19][j] = -2;
				strat[20][j] = -1 - (j - *be - 5 == 0);
			}
		}
	}
	return strat;
}

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