#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; }
vector<vector<int>> devise_strategy(int N) {
int nbits = 13; // 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, lastab = 0
auto lastab = (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] = !lastab;
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 value
for (int v = 1; v <= N; ++v) {
bool prevselfset = (v >> bitpos) & 1;
if (prevselfset && !b) {
s[i][v] = lastab ? -2 : -1;
} else if (!prevselfset && b) {
s[i][v] = lastab ? -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] = lastab ? -2 : -1;
} else {
s[i][v] = lastab ? -1 : -2;
}
}
if (DEBUG > 22)
printf(" s[%d][%d] = %d\n", i, v, s[i][v]);
}
}
}
// whiteboard is always 0 initially
bool startab = 0;
s[0][0] = startab;
for (int v = 1; v <= N; ++v) {
bool selfset = (v >> (nbits - 1)) & 1;
if (nbits == 13 && selfset && !(v >> (nbits - 3))) {
// if the MSB is set to 1, then the 2 following bits MUST be 0
// otherwise, the number will be greater than 5000
s[0][v] = pack(2, 0);
} else {
s[0][v] = pack(0, selfset);
}
}
// If the value is 1, then it's the least
s[0][1] = -1;
// vice-versa
s[0][N] = -2;
if (DEBUG > 1) {
vector<bool> visited(x, false);
for (int i = 0; i < x; ++i) {
for (int v = 1; v <= N; ++v) {
if (DEBUG > 2)
printf("%d %d\n", i, s[i][v]);
if (s[i][v] >= 0)
visited[s[i][v]] = true;
}
}
for (int i = 1; i < x; ++i) {
if (!visited[i])
printf("[!] Unvisited: %d\n", i);
}
}
if (DEBUG)
printf("maxi: %d\n", maxi);
return s;
}
