Submission #1037390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037390		42kangaroo	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	8 ms	1216 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<pair<int, bool>> in;
	vector<int> sis{1700, 566, 188, 62, 20, 6};
	strat[0][0] = 1;
	strat[0][1] = -2;
	in.insert({1, false});
	in.insert({5102, true});
	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<pair<int, bool>> nex;
		for (int j = 1; j <= N; ++j) {
			auto ne = in.lower_bound({j, false});
			if (ne->first == j) {
				strat[1 + 3*i][j] = strat[2 + 3*i][j] = strat[3 + 3*i][j] = -2 + (ne->second == i%2);
			} else {
				auto be = prev(ne);
				if ((j - be->first - 1)/sis[i] == 0) {
					strat[2 + 3*i][j] = strat[3 + 3*i][j] = -1 - i%2;
					if (j == be->first + 1) {
						nex.push_back({j, false});
						strat[1 + 3*i][j] = -1 - i%2;
					} else if ((j - be->first)/sis[i] == 1) {
						nex.push_back({j, true});
						strat[1 + 3*i][j] = -2 + i%2;
					} else {
						strat[1 + 3*i][j] = 4 + 3*i + (j - be->first - 2)/sis[i + 1];
					}
				} else if ((j - be->first - 1)/sis[i] == 1) {
					strat[3 + 3*i][j] = -1 - i%2;
					strat[1 + 3*i][j] = -2 + i%2;
					if (j == be->first + sis[i] + 1) {
						nex.push_back({j, false});
						strat[2 + 3*i][j] = -1 - i%2;
					} else if ((j - be->first)/sis[i] == 2) {
						nex.push_back({j, true});
						strat[2 + 3*i][j] = -2 + i%2;
					} else {
						strat[2 + 3*i][j] = 4 + 3*i + (j - be->first - 2 - sis[i])/sis[i + 1];
					}
				} else {
					strat[2 + 3*i][j] = strat[1 + 3*i][j] = -2 + i%2;
					if (j == be->first + 1 + 2*sis[i]) {
						nex.push_back({j, false});
						strat[3 + 3*i][j] = -1 - i%2;
					} else if ((j - be->first)/sis[i] == 3) {
						nex.push_back({j, true});
						strat[3 + 3*i][j] = -2 + i%2;
					} else {
						strat[3 + 3*i][j] = 4 + 3*i + (j - be->first - 2 - 2*sis[i])/sis[i + 1];
					}
				}
			}
		}
		in.insert(nex.begin(), nex.end());
	}
	strat[16][0] = strat[17][0] = strat[18][0] = 1;
	vector<pair<int, bool>> nex;
	for (int j = 1; j <= N; ++j) {
		auto ne = in.lower_bound({j, false});
		if (ne->first == j) {
			strat[16][j] = strat[17][j] = strat[18][j] = -2 + ne->second;
		} else {
			auto be = prev(ne);
			if ((j - be->first - 1)/6 == 0) {
				strat[17][j] = strat[18][j] = -2;
				if (j == be->first + 1) {
					nex.push_back({j, false});
					strat[16][j] = -2;
				} else if ((j - be->first)/6 == 1) {
					nex.push_back({j, true});
					strat[16][j] = -1;
				} else {
					strat[16][j] = 19 + (j - be->first - 2)/2;
				}
			} else if ((j - be->first - 1)/6 == 1) {
				strat[18][j] = -2;
				strat[16][j] = -1;
				if (j == be->first + 7) {
					nex.push_back({j, false});
					strat[17][j] = -2;
				} else if ((j - be->first)/6 == 2) {
					nex.push_back({j, true});
					strat[17][j] = -1;
				} else {
					strat[17][j] = 19 + (j - be->first - 8)/2;
				}
			} else {
				strat[17][j] = strat[16][j] = -1;
				if (j == be->first + 13) {
					nex.push_back({j, false});
					strat[18][j] = -2;
				} else if ((j - be->first)/6 == 3) {
					nex.push_back({j, true});
					strat[18][j] = -1;
				} else {
					strat[18][j] = 19 + (j - be->first - 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, false});
		if (ne->first == j) {
			strat[19][j] = strat[20][j] = -1 - ne->second;
		} else {
			auto be = prev(ne);
			if ((j - be->first - 1)/2 == 0) {
				strat[20][j] = -1;
				strat[19][j] = -1 - (j - be->first - 2 == 0); 
			} else {
				strat[19][j] = -2;
				strat[20][j] = -1 - (j - be->first - 4 == 0);
			}
		}
	}
	return strat;
}

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