#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 used[10010];
int nxt;
int create_state(int state, int bit, int val)
{
///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 mark = ++ nxt;
if (bit % 2 == 1)
{
cur_strategy[0] = 1;
for (int j = 1; j <= _N; j ++)
{
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 (used[j - 1] != 0)
{
cur_strategy[j] = -2;
used[j] = mark;
continue;
}
if (used[j + 1] != 0)
{
cur_strategy[j] = -1;
used[j] = mark;
continue;
}
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);
}
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);
}
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);
}
cur_strategy[j] = state_index[bit - 1][2];
}
}
}
}
else
{
cur_strategy[0] = 0;
for (int j = 1; j <= _N; j ++)
{
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);
}
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);
}
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);
}
cur_strategy[j] = state_index[bit - 1][2];
}
}
}
}
for (int j = 1; j <= _N; j ++)
if (used[j] == mark)
used[j] = 0;
strategy[state] = cur_strategy;
return state;
}
void init_state()
{
vector < int > base(_N + 1);
strategy.emplace_back();
base[0] = 0;
used[0] = used[5001] = 1;
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);
}
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);
}
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);
}
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;
}
