#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, int ab) {
return ((pos + 1) << 2) | ((b & 1) << 1) | ((ab & 1) << 0);
}
vector<vector<int>> devise_strategy(int N) {
int nbits = log2(N);
int x = (nbits << 2) | 0b111;
// printf("x = %d, nbits = %d\n", x, nbits);
vector<vector<int>> s(x + 1, vector<int>(N + 1));
for (int pos = nbits - 1; pos >= 0; --pos) {
// previously inspected bit
for (int b = 0; b <= 1; ++b) {
// ab = 0 => bag a
// ab = 1 => bag b
// previously inspected
for (int ab = 0; ab <= 1; ++ab) {
int i = pack(pos, b, ab);
// Inspect the other bag next
s[i][0] = !ab;
for (int v = 1; v <= N; ++v) {
// printf("pos: %d b: %d ab: %d v: %d\n", pos, b, ab, v);
// If this is B -> we have checked A at the same bit
if (!ab) {
bool selfset = (v >> pos) & 1;
if (selfset && !b) {
// if the bag we previously inspected did not have bit at pos set,
// but we do
s[i][v] = -1;
} else if (!selfset && b) {
// vice-versa
s[i][v] = -2;
} else if (pos != 0) {
// Move to a lesser significant bit. Say we are at B.
s[i][v] = pack(pos, 0 /* don't care */, 1);
} else {
// how?
}
} else if (pos != 0) {
bool selfset = (v >> (pos - 1)) & 1;
// We were at B, so move to A. We check at push to whiteboard
s[i][v] = pack(pos - 1, selfset, 0);
}
// printf(" s[%d][%d] = %d\n", i, v, s[i][v]);
}
}
}
}
// whiteboard is always 0 initially, so inspect A
s[0][0] = 0;
for (int v = 1; v <= N; ++v) {
bool selfset = (v >> (nbits - 1)) & 1;
s[0][v] = pack(nbits - 1, selfset, 0);
}
return s;
}
