#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
vector < vector < int > > strategy;
int pw[10], _N, state_index[10][3];
const int maxbit = 8;
int create_state(int state, int bit, int val, int left, int right)
{
///cout << state << " " << bit << " " << val << endl;
vector < int > cur_strategy(_N + 1);
if (bit == 0)
{
cur_strategy[0] = 0;
for (int j = 1; j <= _N; j ++)
{
if (j % 3 > val)
cur_strategy[j] = -2;
else
cur_strategy[j] = -1;
}
strategy[state] = cur_strategy;
return state;
}
int mid1 = -1, mid2 = -1;
for (int j = right; j >= left; j --)
{
int val = ((j % pw[bit]) / pw[bit - 1]);
if (val == 2)
mid2 = j;
if (val == 1)
mid1 = j;
}
if (bit % 2 == 1)
{
cur_strategy[0] = 1;
for (int j = 1; j <= _N; j ++)
{
if (j == left)
{
cur_strategy[j] = -2;
continue;
}
if (j == right)
{
cur_strategy[j] = -1;
continue;
}
int cur_val = ((j % pw[bit + 1]) / pw[bit]);
if (cur_val < val)
cur_strategy[j] = -2;
else if (cur_val > val)
cur_strategy[j] = -1;
else
{
cur_val = ((j % pw[bit]) / pw[bit - 1]);
if (bit == 1)
{
if (cur_val == 0)
{
cur_strategy[j] = -2;
continue;
}
if (cur_val == 2)
{
cur_strategy[j] = -1;
continue;
}
}
if (cur_val == 0)
{
if (state_index[bit - 1][0] == -1)
{
strategy.emplace_back();
state_index[bit - 1][0] = create_state(strategy.size() - 1, bit - 1, 0, left, mid1 - 1);
}
cur_strategy[j] = state_index[bit - 1][0];
}
else if (cur_val == 1)
{
if (state_index[bit - 1][1] == -1)
{
strategy.emplace_back();
state_index[bit - 1][1] = create_state(strategy.size() - 1, bit - 1, 1, mid1, mid2 - 1);
}
cur_strategy[j] = state_index[bit - 1][1];
}
else
{
if (state_index[bit - 1][2] == -1)
{
strategy.emplace_back();
state_index[bit - 1][2] = create_state(strategy.size() - 1, bit - 1, 2, mid2, right);
}
cur_strategy[j] = state_index[bit - 1][2];
}
}
}
}
else
{
cur_strategy[0] = 0;
for (int j = 1; j <= _N; j ++)
{
if (j == left)
{
cur_strategy[j] = -1;
continue;
}
if (j == right)
{
cur_strategy[j] = -2;
continue;
}
int cur_val = ((j % pw[bit + 1]) / pw[bit]);
///cout << state << " --- " << bit << " " << " " << cur_val << endl;
if (cur_val < val)
{
///cout << "here " << bit << " " << val << " " << cur_val << endl;
cur_strategy[j] = -1;
}
else if (cur_val > val)
{
///cout << "there " << bit << " " << val << " " << cur_val << endl;
cur_strategy[j] = -2;
}
else
{
cur_val = ((j % pw[bit]) / pw[bit - 1]);
if (cur_val == 0)
{
if (state_index[bit - 1][0] == -1)
{
strategy.emplace_back();
state_index[bit - 1][0] = create_state(strategy.size() - 1, bit - 1, 0, left, mid1 - 1);
}
cur_strategy[j] = state_index[bit - 1][0];
}
else if (cur_val == 1)
{
if (state_index[bit - 1][1] == -1)
{
strategy.emplace_back();
state_index[bit - 1][1] = create_state(strategy.size() - 1, bit - 1, 1, mid1, mid2 - 1);
}
cur_strategy[j] = state_index[bit - 1][1];
}
else
{
if (state_index[bit - 1][2] == -1)
{
strategy.emplace_back();
state_index[bit - 1][2] = create_state(strategy.size() - 1, bit - 1, 2, mid2, right);
}
cur_strategy[j] = state_index[bit - 1][2];
}
}
}
}
strategy[state] = cur_strategy;
return state;
}
void init_state()
{
vector < int > base(_N + 1);
strategy.emplace_back();
base[0] = 0;
int mid1 = 0, mid2 = 0;
for (int j = _N; j > 0; j --)
{
int val = (j % pw[maxbit]) / pw[maxbit - 1];
if (val == 1)
mid1 = j;
if (val == 2)
mid2 = j;
}
for (int j = 1; j <= _N; j ++)
{
int val = (j % pw[maxbit]) / pw[maxbit - 1];
if (val == 0)
{
if (state_index[7][0] == -1)
{
strategy.emplace_back();
state_index[7][0] = create_state(strategy.size() - 1, 7, 0, 1, mid1 - 1);
}
base[j] = state_index[7][0];
}
else if (val == 1)
{
if (state_index[7][1] == -1)
{
strategy.emplace_back();
state_index[7][1] = create_state(strategy.size() - 1, 7, 1, mid1, mid2 - 1);
}
base[j] = state_index[7][1];
}
else
{
if (state_index[7][2] == -1)
{
strategy.emplace_back();
state_index[7][2] = create_state(strategy.size() - 1, 7, 2, mid2, 5000);
}
base[j] = state_index[7][2];
}
}
strategy[0] = base;
}
vector<std::vector<int>> devise_strategy(int N)
{
_N = N;
for (int i = 0; i < 10; i ++)
for (int j = 0; j < 3; j ++)
state_index[i][j] = -1;
pw[0] = 1;
for (int i = 1; i < 10; i ++)
pw[i] = pw[i - 1] * 3;
init_state();
///create_state(0, 7);
/**for (int i = 0; i < strategy.size(); i ++, cout << endl)
for (int j = 0; j <= N; j ++)
cout << strategy[i][j] << " ";
cout << endl;*/
return strategy;
}
