#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> devise_strategy(int N) {
int nbBits = 8;
vector<int> puissances(nbBits);
puissances[0] = 1;
for (int i = 1; i < nbBits; ++i)
puissances[i] = 3 * puissances[i - 1];
int k = 3 * nbBits + 1;
vector<int> states;
states.push_back(0);
for (int i = 1; i < k; ++i) {
int bit = (i - 1) % nbBits;
int val = (i - 1) / nbBits;
if (bit or val == 1)
states.push_back(i);
}
k = states.size();
vector<vector<int>> strategy(k, vector<int>(N + 1));
auto getBit = [&](int x, int bit) { return x / puissances[bit] % 3; };
auto getId = [&](int x) {
return lower_bound(states.begin(), states.end(), x) - states.begin();
};
for (int i = 0; i < k; ++i) {
int s = states[i];
if (s == 0) {
strategy[i][0] = !((nbBits - 1) % 2);
for (int j = 0; j < N; ++j)
strategy[i][j + 1] =
getId(1 + getBit(j, nbBits - 1) * nbBits + nbBits - 1);
} else {
int bit = (s - 1) % nbBits;
int val = (s - 1) / nbBits;
strategy[i][0] = bit % 2;
for (int j = 0; j < N; ++j) {
int v = getBit(j, bit);
if (v < val)
strategy[i][j + 1] = -1 - bit % 2;
else if (v > val)
strategy[i][j + 1] = -2 + bit % 2;
else if (bit) {
int nxtVal = getBit(j, bit - 1);
if (bit == 1 and nxtVal == 0)
strategy[i][j + 1] = -1 - bit % 2;
else if (bit == 1 and nxtVal == 2)
strategy[i][j + 1] = -2 + bit % 2;
else
strategy[i][j + 1] = getId(1 + nxtVal * nbBits + bit - 1);
}
}
}
}
return strategy;
}
