Submission #1077055

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077055		allin27x	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	29 ms	1116 KiB

prison

#include <bits/stdc++.h>
using namespace std;
const int base  = 3;
const int mp = 8;

int nth_bit(int x, int n){
	if (n<0) return 0;
	vector<int> wr;
	while (x) {
		wr.push_back(x % base);
		x/= base;
	}
	wr.resize(mp+2, 0);
	return wr[n];


}
std::vector<std::vector<int>> devise_strategy(int N){
	vector ans(mp*base-1, vector (N+1, 0));
	ans[0][0] = 0;
	for (int i = 1; i <= N; i++) {
		int bit = nth_bit(i, mp - 1);
		ans[0][i] = bit + 1;
	}
	for (int i=1; i < mp*base-1; i++) {
		int r = (i-1)/base % 2;
		ans[i][0] = !r;
		int this_bit = (i-1) % base;
		if (i == mp*base - 2) this_bit = 1;
		for (int j=1; j<=N; j++) {
			int other_bit = nth_bit(j, mp - 1 - (i-1)/base);
			int new_bit = nth_bit(j, mp - 2 - (i-1)/base);
			if (this_bit < other_bit) ans[i][j] = -1 - r;
			if (this_bit > other_bit) ans[i][j] = -1 - !r;
			if (this_bit == other_bit) ans[i][j] = ((i-1)/base + 1) * base + 1 + new_bit;
			if ((i-1)/base == mp-2 && this_bit == other_bit) {
				if (new_bit == 0) ans[i][j] = -1 - !r;
				if (new_bit == 2) ans[i][j] = -1 - r;
				if (new_bit == 1) ans[i][j] = mp*base - 2;
			}
			if (ans[i][j] >= mp*base - 1) ans[i][j] = -1;
		}
	}

	return ans;
}

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