#include "prison.h"
#include <vector>
#include <iostream>
#include <cassert>
#include <algorithm>
using namespace std;
int get_bit(int x, int bit, int base=2) {
vector<int> lst;
while(x>0) {
lst.push_back(x%base);
x/=base;
}
return (bit>=(int)lst.size()?0:lst[bit]);
}
std::vector<std::vector<int>> devise_strategy(int N) {
//~ cerr<<get_bit(4, 0)<<"\n";
//~ exit(0);
const int BASE=2;
const int START=12;
int x=24;
std::vector<std::vector<int>> s(x+1, std::vector<int>(N+1, 0));
//~ cerr<<"digraph G {\n";
for(int i=0;i<=x;++i) {
if(i==0) {
s[i][0]=0;
for(int j=1;j<=N;++j) {
s[i][j]=1+get_bit(j, START, BASE);
//~ cerr<<i<<" -> "<<s[i][j]<<"\n";
}
}else {
int bit=START-(i-1)/BASE;
int bag=(bit&1)^1;
int have=(i-1)%BASE;
s[i][0]=bag;
int THIS=bag==0?-1:-2;
int OTHER=bag==0?-2:-1;
for(int j=1;j<=N;++j) {
int curr=get_bit(j,bit, BASE);
if(curr>have) {
s[i][j]=OTHER;
}else if(curr<have) {
s[i][j]=THIS;
}else {
int nxt=get_bit(j, bit-1, BASE);
//~ std::cerr<<i<<" "<<j<<" "<<bit-1<<" "<<nxt<<"!!\n";
if(bit-1==0) {
if(nxt==0) {
s[i][j]=THIS;
}else {
s[i][j]=OTHER;
}
}else {
//~ std::cerr<<i<<" "<<2*(bit+1)+1+nxt<<"\n";
//~ assert(i!=2*(12-bit+1)+1+nxt);
s[i][j]=BASE*(START-bit+1)+1+nxt;
//~ cerr<<i<<" -> "<<s[i][j]<<"\n";
}
}
}
}
}
//~ cerr<<"}\n";
return s;
}
//~ 0 -> 1 2
//~ 1 -> 3 4
//~ 2 -> 5 6
