Submission #631034

#	Time	Username	Problem	Language	Result	Execution time	Memory
631034		rainboy	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	19 ms	1108 KiB

prison

/* https://ioi2022.id/data/editorial.pdf */
#include "prison.h"
#include <vector>

using namespace std;

typedef vector<int> vi;

const int N = 5000, K = 20, L = 9;

int max(int a, int b) { return a > b ? a : b; }

int nn[K + 1], cc[K + 1], kk[L + 1], dd[N + 1][L];

void init() {
	nn[0] = 2;
	for (int k = 1; k <= K; k++)
		for (int c = 1; c <= k; c++) {
			int n = nn[k - c] * c + 2;
			if (nn[k] < n)
				nn[k] = n, cc[k] = c;
		}
	int l = 0;
	for (int k = K; k > 0; k -= cc[k])
		kk[l++] = k;
	kk[l++] = 0;
	for (int i = 1; i <= N; i++)
		for (int h = 0, i_ = i - 1; h < l; h++) {
			int k = kk[h], k_ = kk[h + 1];
			if (i_ == 0) {
				dd[i][h] = -1;
				break;
			} else if (i_ == nn[k] - 1) {
				dd[i][h] = cc[k];
				break;
			} else {
				dd[i][h] = (i_ - 1) / nn[k_];
				i_ = (i_ - 1) % nn[k_];
			}
		}
}

vector<vi> devise_strategy(int n) {
	init();
	vector<vi> ttt;
	for (int g = 0, h = 1; g <= L; g++) {
		int c = g == 0 ? 1 : cc[kk[g - 1]], c_ = cc[kk[g]];
		for (int d = 0; d < c; d++) {
			vi tt(n + 1, 0);
			tt[0] = g % 2;
			for (int i = 1; i <= n; i++)
				if (g > 0 && dd[i][g - 1] != d)
					tt[i] = (g % 2 == 0) == (dd[i][g - 1] < d) ? -1 : -2;
				else if (dd[i][g] == -1)
					tt[i] = g % 2 == 0 ? -1 : -2;
				else if (dd[i][g] == c_)
					tt[i] = g % 2 != 0 ? -1 : -2;
				else
					tt[i] = h + dd[i][g];
			ttt.push_back(tt);
		}
		h += c_;
	}
	return ttt;
}

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