Submission #626988

#	Time	Username	Problem	Language	Result	Execution time	Memory
626988		timmyfeng	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	17 ms	1040 KiB

prison

#include "prison.h"

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

vector<vector<int>> devise_strategy(int n) {
	const int M = 20, N = 5102;

	int xl = 0, xr = 1;
	vector strat(M + 1, vector<int>(N));
	vector<int> mapping(N), div = {3, 3, 3, 3, 3, 3, 2, 0};
	for (int k = 0; k < (int) div.size(); ++k) {
		for (int l = 0, r = 0; l < N; l = r) {
			while (r < N && mapping[r] == mapping[l]) ++r;
			for (int x = xl; x < xr; ++x) {
				if (mapping[l] < x) {
					fill(strat[x].begin() + l, strat[x].begin() + r, -1);
				} else if (mapping[l] > x) {
					fill(strat[x].begin() + l, strat[x].begin() + r, INT_MAX);
				} else {
					strat[x][l] = -1, strat[x][r - 1] = INT_MAX;
					for (int i = l + 1; i < r - 1; ++i) {
						strat[x][i] = xr + div[k] * (i - l - 1) / (r - l - 2);
					}
				}
			}
		}
		for (int i = 0; i < N; ++i) {
			if (xl <= mapping[i] && mapping[i] < xr) {
				mapping[i] = strat[mapping[i]][i];
			}
		}
		for (int x = xl; x < xr; ++x) {
			strat[x].resize(n);
			for (auto &y : strat[x]) if (y == INT_MAX) y = -2;
			strat[x].insert(strat[x].begin(), k % 2);
			if (k % 2) for (auto &y : strat[x]) if (y < 0) y = -3 - y;
		}
		xl = xr, xr += div[k];
	}
	return strat;
}

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