#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<std::vector<int>> devise_strategy(int N)
{
int n = 5000;
vector<int> range = {5000, 1666, 555, 185, 61, 20, 6, 2}; //Sizes of the blocks (7 elements)
vector<vector<int>> output(21, vector<int> (n+1));
for(int i = 0; i <= 20; i++)
{
int bit = (i+2)/3;
output[i][0] = bit%2;
int indval = (i == 0) ? 0 : (i-1)%3; //Val of bit according to index i
for(int j = 1; j <= n; j++)
{
int k = j; //Value in range from 1 to range[bit]
int val = 0; //Value of the previous bit
for(int a = 0; a < bit; a++)
{
k--; //We can exclude the smallest value
if(k <= 0)
{
break;
}
val = (k-1)/range[a+1];
k = 1+(k-1)%range[a+1]; //Break down to the new range
}
if(k <= 0)
{
output[i][j] = -1-(bit%2);
continue;
}
if(val < indval || (val == indval && k == 1))
{
//Current bag is smaller
output[i][j] = -1-(bit%2);
}
else if(val > indval || (val == indval && k == range[bit]))
{
//Other bag is smaller
output[i][j] = -2+(bit%2);
}
else
{
//Answer lies in the next block!
k--;
int nval = (k-1)/range[bit+1]; //Value of the next bit
output[i][j] = 3*bit + 1 + nval;
}
}
}
for(int i = 0; i <= 20; i++)
{
while((int) output[i].size() > N+1)
{
output[i].pop_back();
}
}
return output;
}
