Submission #833528

#	Time	Username	Problem	Language	Result	Execution time	Memory
833528		pavement	Prisoner Challenge (IOI22_prison)	C++17	42.50 / 100	19 ms	1500 KiB

prison

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

#define mp make_pair

using ii = pair<int, int>;

vector<vector<int> > devise_strategy(int N) {
	auto ceil_log = [&](int n, int k) {
		int ret = 0, tmp = 1;
		while (tmp < n) {
			tmp *= k;
			ret++;
		}
		return ret;
	};
	
	int min_sf = (int)1e9, base = -1, b = -1;
	
	for (int i = 2; i <= N; i++) {
		int j = ceil_log(N - 1, i);
		if (min_sf > (i + 1) * (j + 1) - 1) {
			min_sf = (i + 1) * (j + 1) - 1;
			base = i;
			b = j;
		}
	}
	
	int x = min_sf;
	vector<vector<int> > s(x + 1, vector<int>(N + 1));
	
	auto unpack = [&](int v) {
		int b_bit = v / (base + 1), state = v % (base + 1);
		return mp(b - b_bit, state);
	};
	
	auto pack = [&](int bit, int state) {
		int tmp = (b - bit) * (base + 1) + state;
		assert(0 <= tmp && tmp <= x);
		return tmp;
	};
	
	auto get_digit = [&](int num, int pos) {
		while (pos--) {
			num /= base;
		}
		return num % base;
	};
		
	for (int i = 0; i <= x; i++) {
		auto [bit, state] = unpack(i);
		if (state == 0) {
			s[i][0] = 0;
			for (int j = 1; j <= N; j++) {
				// find digit at position bit of j
				int digit = get_digit(j - 1, bit);
				assert(0 <= digit && digit < base);
				// write (bit, digit + 1)
				s[i][j] = pack(bit, digit + 1);
			}
		} else {
			s[i][0] = 1;
			for (int j = 1; j <= N; j++) {
				// find digit at position bit of j
				int digit = get_digit(j - 1, bit);
				if (digit == state - 1) {
					if (bit == 0) {
						s[i][j] = 0;
					} else {
						// write (bit - 1, 0)
						s[i][j] = pack(bit - 1, 0);
					}
				} else if (digit > state - 1) {
					s[i][j] = -1;
				} else {
					s[i][j] = -2;
				}
			}
		}
	}
	return s;
}

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