#include"prison.h"
#include<vector>
using namespace std;
vector<vector<int>>strats;
int n;
int to_neg(int bag){
return -1-(bag^1);
}
int get_strat(int bit,int prev_bit,int prev_bag){
int curr_strat=(int)strats.size();
strats.push_back(vector<int>(n+1));
int inspected_bag=prev_bag^1;
strats[curr_strat][0]=inspected_bag;
if(bit==0){
for(int i=1;i<=n;i++){
if(i%2==1){
strats[curr_strat][i]=to_neg(inspected_bag);
}else{
strats[curr_strat][i]=to_neg(prev_bag);
}
}
return curr_strat;
}
int strat0=get_strat(bit-1,0,prev_bag^1);
int strat1=get_strat(bit-1,1,prev_bag^1);
for(int i=1;i<=n;i++){
bool curr_bit=(i&(1<<bit))!=0;
if(curr_bit!=prev_bit){
if(curr_bit){
strats[curr_strat][i]=to_neg(inspected_bag);
}else{
strats[curr_strat][i]=to_neg(prev_bag);
}
}else{
bool next_bit=(i&(1<<(bit-1)))!=0;
if(next_bit==0){
strats[curr_strat][i]=strat0;
}else{
strats[curr_strat][i]=strat1;
}
}
}
return curr_strat;
}
vector<vector<int>>devise_strategy(int N){
n=N;
strats.push_back(vector<int>(n+1));
int strat0=get_strat(13,0,0);
int strat1=get_strat(13,1,0);
for(int i=1;i<=n;i++){
if(i&(1<<13)){
strats[0][i]=strat1;
}else{
strats[0][i]=strat0;
}
}
return strats;
}
