#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
#define bv(x, i) (((x) & (1 << (i))) ? 1 : 0)
using vi = vector<int>;
using vvi = vector<vi>;
struct State {
int bitID, id;
// if id = 0, then current bag is A
// if id = 1, then current bag is B, and A[bit] = 0
// if id = 2, then current bag is B, and A[bit] = 1
};
const int BITS = 13;
vector<State> states;
int stateID[BITS][3];
void build_state_table() {
for (int i = BITS - 1; i >= 0; i--) {
for (int state = 0; state < 3; state++) {
stateID[i][state] = (int) states.size();
states.push_back(State {i, state});
}
}
}
int transition(State current, int bagValue) {
State newState = current;
if (current.id == 0) {
newState.id = 1 + bv(bagValue, current.bitID);
newState.bitID = current.bitID;
} else {
if (current.id - 1 != bv(bagValue, current.bitID)) {
return bv(bagValue, current.bitID) == 1 ? -1 : -2;
} else {
newState.id = 0;
newState.bitID = current.bitID - 1;
if (newState.bitID < 0) return -1; // shouldnt happen
}
}
return stateID[newState.bitID][newState.id];
}
vvi devise_strategy(int N) {
vvi s(BITS * 3, vi(N+1, 0));
build_state_table();
for (int i = 0; i < BITS * 3; i++) {
State cur = states[i];
s[i][0] = cur.id == 0 ? 0 : 1;
for (int j = 1; j <= N; j++) {
s[i][j] = transition(cur, j);
}
}
return s;
}
