#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
const int x = 20;
vector<int> divs = {3, 3, 3, 3, 3, 2, 2, 1};
vector<int> indexs = {1, 4, 7, 10, 13, 16, 18, 20};
vector<int> AorB = {0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0};
int index0toOther(int AB) //0 - -1 1 - -2
{
if(AB == 0) return -1;
return -2;
}
void solve(int l, int r, int num, int index, vector<vector<int>>& table)
{
int n = r - l + 1;
if(n <= 2)
{
table[num][l] = index0toOther(AorB[num]);
table[num][r] = index0toOther(1 - AorB[num]);
return;
}
int intervalSize = (n + divs[index] - 3) / divs[index]; //n - 2 + divs[index] - 1;
for(int i = l; i <= r; i++)
{
if(i == l) table[num][i] = index0toOther(AorB[num]);
else if(i == r) table[num][i] = index0toOther(1 - AorB[num]);
else
{
int numInterval = (i - l - 1) / intervalSize;
table[num][i] = indexs[index] + numInterval;
}
}
for(int i = 0; i < divs[index]; i++)
{
int nnum = indexs[index] + i;
int nl = l + 1 + intervalSize * i, nr = min(r, l + intervalSize * (i + 1));
for(int ii = l; ii < nl; ii++)
{
table[nnum][ii] = index0toOther(1 - AorB[num]);
}
solve(nl, nr, nnum, index + 1, table);
for(int ii = nr+1; ii <= r; ii++)
{
table[nnum][ii] = index0toOther(AorB[num]);
}
}
}
vector<vector<int>> devise_strategy(int N)
{
vector<vector<int>> res(x + 1);
for(int i = 0; i <= x; i++)
{
res[i] = vector<int>(N + 1);
res[i][0] = AorB[i];
}
solve(1, N, 0, 0, res);
return res;
}
