#include "prison.h"
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
constexpr int DEBUG = 0;
int log2(int v) {
int r = 0;
while (v >>= 1) {
r++;
}
return r + 1;
}
int pack(int pos, int b) { return (((pos) << 1) | ((b & 1) << 0)) + 1; }
/*
int pack(int pos, int b) {
int p = packi(pos, b);
if (mapping[p] != -1)
return mapping[p];
mapping[p] = mapn;
return mapn++;
}*/
vector<vector<int>> devise_strategy(int N) {
int nbits = log2(N);
int x = ((nbits - 1) << 1) | 0b1;
if (DEBUG)
printf("nbits: %d, x: %d\n", nbits, x);
vector<vector<int>> s(x, vector<int>(N + 1));
int maxi = 0;
// pos -> previous pos
for (int pos = 0; pos < nbits - 1; ++pos) {
int bitpos = nbits - 1 - pos;
// b -> previously inspected bit
for (int b = 0; b <= 1; ++b) {
// IF we last checked A, lasta = 0
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;
if (DEBUG > 1)
printf("[%d] prev pos: %d, prev bitpos: %d, prev b: %d -> check: %d\n",
i, pos, bitpos, b, s[i][0]);
// v -> the current
for (int v = 1; v <= N; ++v) {
bool prevselfset = (v >> bitpos) & 1;
if (prevselfset && !b) {
s[i][v] = lasta ? -2 : -1;
} else if (!prevselfset && b) {
s[i][v] = lasta ? -1 : -2;
} else if (bitpos > 1) {
bool selfset = (v >> (bitpos - 1)) & 1;
s[i][v] = pack(pos + 1, selfset);
} else {
bool selfset = v & 1;
if (selfset) {
s[i][v] = lasta ? -2 : -1;
} else {
s[i][v] = lasta ? -1 : -2;
}
}
if (DEBUG > 2)
printf(" s[%d][%d] = %d\n", i, v, s[i][v]);
}
}
}
if (DEBUG > 1)
printf("---\n");
// whiteboard is always 0 initially
bool starta = 0;
s[0][0] = starta;
for (int v = 1; v <= N; ++v) {
bool selfset = (v >> (nbits - 1)) & 1;
s[0][v] = pack(0, selfset);
if (DEBUG > 2)
printf(" s[%d][%d] = %d\n", 0, v, s[0][v]);
}
// If the value is 1, then it's the least
s[0][1] = -1;
// vice-versa
s[0][N] = -2;
if (DEBUG)
printf("maxi: %d\n", maxi);
return s;
}
