#include "prison.h"
#include <iostream>
#include <vector>
using namespace std;
vector < vector < int > > devise_strategy(int n)
{
int lg = 1;
int cur = 2;
while(cur <= n)
{
lg++;
cur *= 2;
}
vector < vector < int > > ans;
ans.resize(3 * lg);
for(int reads = 0; reads < 3 * lg; reads++)
{
ans[reads].resize(n + 1, 0);
}
for(int reads = 0; reads < 3 * lg; reads++)
{
int whole = reads / 3;
int remainder = reads % 3;
if(remainder == 0)
{
ans[reads][0] = 0; // cheta A
for(int sees = 1; sees <= n; sees++)
{
int which = lg - whole - 1;
bool bitb = (bool)(sees & (1 << which));
int writes = reads + bitb + 1; // pri A % 2 == 0 -> napisanoto + 1 (ostatuk 1), pri A % 2 == 1 -> napisanoto + 2 (ostatuk 2)
ans[reads][sees] = writes;
}
}
else
{
ans[reads][0] = 1; // cheta B
for(int sees = 1; sees <= n; sees++)
{
bool bita = remainder - 1; // ostatuk na napisanoto 1 -> A % 2 == 0, pri ostatuk na napisanoto 2 -> A % 2 == 1
int which = lg - whole - 1;
bool bitb = (bool)(sees & (1 << which));
if(bita < bitb) // A < B
ans[reads][sees] = -1;
else if(bita > bitb) // A > B
ans[reads][sees] = -2;
else // nqmame dostatuchno info
{
if(whole == lg - 1)
ans[reads][sees] = 0;
else
ans[reads][sees] = 3 * (whole + 1);
}
}
}
}
return ans;
}
