Submission #833844

#	Time	Username	Problem	Language	Result	Execution time	Memory
833844		pavement	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	10 ms	980 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 base = 3, b = ceil_log(4999, base) - 1, x = base * (b + 1) - 2;
	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;
		if (b - b_bit == 0) {
			assert(state == 0);
			state++;
		}
		return mp(b - b_bit, state);
	};
	
	auto pack = [&](int bit, int state) {
		int tmp = (b - bit) * base + state + 1;
		if (bit == 0) {
			assert(state == 1);
			tmp--;
		}
		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);
						if (bit - 1 == 0 && next_digit != 1) {
							if (next_digit == 0) {
								s[i][j] = (bit % 2 ? -1 : -2);
							} else if (next_digit == 2) {
								s[i][j] = (bit % 2 ? -2 : -1);
							}
						} else {
							// 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: 70 / 90