#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
int log2(int v) {
int r = 0;
while (v >>= 1) {
r++;
}
return r + 1;
}
int pack(int pos, int b) { return ((pos + 1) << 1) | ((b & 1) << 0); }
vector<vector<int>> devise_strategy(int N) {
int nbits = log2(N);
int x = (nbits << 1) | 0b1;
// printf("x = %d, nbits = %d\n", x, nbits);
vector<vector<int>> s(x + 1, vector<int>(N + 1));
int maxi = 0;
// pos -> previous pos
for (int pos = nbits - 1; pos >= 0; --pos) {
// b -> previously inspected bit
for (int b = 0; b <= 1; ++b) {
// IF we last checked A
auto lasta = (pos % 2);
int i = pack(pos, b);
maxi = max(i, maxi);
// IF we last checked A -> check B next, and vice-versa
s[i][0] = !lasta;
// v -> the current
for (int v = 1; v <= N; ++v) {
bool prevselfset = (v >> pos) & 1;
if (prevselfset && !b) {
s[i][v] = lasta ? -2 : -1;
} else if (!prevselfset && b) {
s[i][v] = lasta ? -1 : -2;
} else if (pos > 0) {
bool selfset = (v >> (pos - 1)) & 1;
s[i][v] = pack(pos - 1, selfset);
}
}
}
}
// whiteboard is always 0 initially
s[0][0] = !(nbits % 2);
for (int v = 1; v <= N; ++v) {
bool selfset = (v >> (nbits - 1)) & 1;
s[0][v] = pack(nbits - 1, selfset);
}
// printf("maxi: %d\n", maxi);
return s;
}
