Submission #1077044

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077044		allin27x	Prisoner Challenge (IOI22_prison)	C++17	65 / 100	32 ms	1184 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; i++) {
		int r = (i-1)/base % 2;
		ans[i][0] = !r;
		int this_bit = (i-1) % base;
		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 (ans[i][j] > mp*base) ans[i][j] = -1;
		}
	}

	return ans;
}

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