#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int it[21] = {-1, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 6, 6, 7},
part[21] = {-1, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 0, 1, 0},
d[8] = {3, 3, 3, 3, 3, 2, 2, 1},
N_MAX = 5588;
int get_part(pair<int, int> const &range, int n, int iteration)
{
return (n - (range.first + 1)) / d[iteration];
}
pair<int, int> get_subrange(pair<int, int> const &range, int part, int iteration)
{
return {range.first + 1 + (part * (range.second - range.first - 1)) / d[iteration],
range.first + ((part + 1) * (range.second - range.first - 1)) / d[iteration]};
}
pair<int, int> reconstruct_range(int n, int iteration)
{
pair<int, int> range = {1, N_MAX};
for (int i = 0; i < iteration; ++i)
{
if (n == range.first || n == range.second)
return {-1, -1}; // We will never reach this state.
range = get_subrange(range, get_part(range, n, i), i);
}
return range;
}
int encode_state(int iteration, int part)
{
int state = 1;
while (it[state] != iteration)
++state;
return state + part;
}
vector<vector<int>> devise_strategy(int N)
{
vector<vector<int>> s(21, vector<int>(N + 1));
for (size_t i = 0; i <= 20; ++i)
{
s[i][0] = !(it[i] & 1);
for (int j = 1; j <= N; ++j)
{
auto [a, b] = reconstruct_range(j, it[i]);
if (a == -1 && b == -1)
continue;
// Check whether it's on the boundary of the common range.
if (j == a)
{
s[i][j] = s[i][0] ? -2 : -1;
continue;
}
if (j == b)
{
s[i][j] = s[i][0] ? -1 : -2;
continue;
}
if (i) // In the first iteration, we don't have a subrange specified by the state.
{
int k = get_part({a, b}, j, it[i]);
int h = part[i];
// If they don't belong to the same part of the subrange, stop.
if (k != h)
{
s[i][j] = (s[i][0] ^ (k > h)) ? -2 : -1;
continue;
}
tie(a, b) = get_subrange({a, b}, h, it[i]); // the other bag's range
// Check whether it's on the boundary of the new range.
if (j == a)
{
s[i][j] = s[i][0] ? -2 : -1;
continue;
}
if (j == b)
{
s[i][j] = s[i][0] ? -1 : -2;
continue;
}
}
assert(it[i] < 7);
s[i][j] = encode_state(it[i] + 1, get_part({a, b}, j, it[i] + 1));
}
}
return s;
}
