#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> segments[8];
vector<int> steps = { 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4 ,4, 5, 5, 5, 6, 6, 6, 7, 7};
int t[8];
void createSegments(int l, int r, int level)
{
t[level] = max(t[level], r - l + 1);
segments[level].emplace_back(l, r);
++l; --r;
if (level == 7) return;
int len = r - l + 1;
if (level <= 5)
{
int k = len / 3;
int a = l + k - 1;
int b = a + k;
if (len % 3 == 2) ++b;
createSegments(l, a, level + 1);
createSegments(a + 1, b, level + 1);
createSegments(b + 1, r, level + 1);
}
else
{
createSegments(l, l + len / 2 - 1, level + 1);
createSegments(l + len / 2, r, level + 1);
}
}
vector<vector<int>> devise_strategy(int N)
{
createSegments(1, 5000, 0);
vector<vector<int>> strategy;
for (int n = 0; n <= 20; ++n)
{
vector<int> current(N + 1);
int step = steps[n];
current[0] = (step & 1);
for (int j = 1; j <= N; ++j)
{
pair<int, int> segment = make_pair(1e9, 1e9);
int idx = 0;
for (int i = 0; i < segments[step].size(); ++i)
{
if (segments[step][i].second >= j)
{
segment = segments[step][i];
if (step == 7) idx = i % 2;
else idx = i % 3;
break;
}
}
if (segment.first > j)
{
for (int i = 0; i < segments[step - 1].size(); ++i)
{
if (segments[step - 1][i].second >= j)
{
segment = segments[step - 1][i];
break;
}
}
if (j == segment.first)
{
if (step & 1)
current[j] = -2;
else
current[j] = -1;
continue;
}
if (j == segment.second)
{
if (step & 1)
current[j] = -1;
else
current[j] = -2;
continue;
}
continue;
}
if (step > 0)
{
int written;
if (step == 7) written = (n - 1) % 2;
else written = (n - 1) % 3;
if (idx < written)
{
if (step & 1)
current[j] = -2;
else
current[j] = -1;
continue;
}
if (idx > written)
{
if (step & 1)
current[j] = -1;
else
current[j] = -2;
continue;
}
}
if (j == segment.first)
{
if (step & 1)
current[j] = -2;
else
current[j] = -1;
continue;
}
if (j == segment.second)
{
if (step & 1)
current[j] = -1;
else
current[j] = -2;
continue;
}
for (int i = 0; i < segments[step + 1].size(); ++i)
{
if (segments[step + 1][i].second >= j)
{
segment = segments[step + 1][i];
if (step == 6) idx = i % 2;
else idx = i % 3;
break;
}
}
current[j] = step * 3 + idx + 1;
}
strategy.push_back(current);
}
return strategy;
}
