Submission #833803

#	Time	Username	Problem	Language	Result	Execution time	Memory
833803		pavement	Prisoner Challenge (IOI22_prison)	C++17	54.50 / 100	16 ms	1236 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 * (j + 1)) {
			min_sf = i * (j + 1);
			base = i;
			b = j;
		}
	}
	
	int x = min_sf;
	vector<vector<int> > s(x + 1, vector<int>(N + 1));
	
	auto unpack = [&](int v) {
		if (v == 0) {
			return mp(b, -1);
		}
		v--;
		int b_bit = v / base, state = v % base;
		return mp(b - b_bit, state);
	};
	
	auto pack = [&](int bit, int state) {
		int tmp = (b - bit) * base + state + 1;
		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 == -1) {
			s[i][0] = bit % 2;
			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)
				s[i][j] = pack(bit, digit);
			}
		} else {
			s[i][0] = !(bit % 2);
			for (int j = 1; j <= N; j++) {
				// find digit at position bit of j
				int digit = get_digit(j - 1, bit);
				if (digit == state) {
					if (bit == 0) {
						s[i][j] = 0;
					} else {
						int next_digit = get_digit(j - 1, bit - 1);
						// write (bit - 1, next_digit)
						s[i][j] = pack(bit - 1, next_digit);
					}
				} else if (digit > state) {
					s[i][j] = (bit % 2 ? -2 : -1);
				} else {
					s[i][j] = (bit % 2 ? -1 : -2);
				}
			}
		}
	}
	return s;
}

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