#include "prison.h"
#include <set>
#include <vector>
#include <iostream>
using namespace std;
const int N = 20005;
int l[N], r[N];
int id[N];
vector <int> children[N];
vector < pair<int, int> > vertices[30];
vector < vector<int> > answ;
int it = 1;
int A;
int max_height = 0;
void rec(int v, int s, int e, int h) {
max_height = max(max_height, h);
///
l[v] = s;
r[v] = e;
///
int len = e - s + 1;
if (len <= 2) return ;
s++;
e--;
len -= 2;
int div = (h == 6) ? 2 : 3;
int rem = len % div;
int cur_start = s;
for (int i = 1; i <= div; i++) {
int cur_len = len / div;
if (rem > 0) {
cur_len++;
--rem;
}
++it;
id[it] = 3 * h + i;
///
vertices[ id[it] ].push_back( make_pair(v, it) );
///
children[v].push_back(it);
rec(it, cur_start, cur_start + cur_len - 1, h + 1);
cur_start += cur_len;
}
}
vector < vector<int> > devise_strategy(int n) {
id[1] = 0;
rec(1, 1, n, 0);
int mx = 20;
answ.resize(mx + 1);
answ[0].resize(n + 1, 0);
answ[0][0] = 0;
answ[0][1] = -1;
answ[0][n] = -2;
for (int i = 2; i < n; i++) {
for (int j = 0; j < (int)children[1].size(); j++) {
int vertex = children[1][j];
if (i >= l[vertex] && i <= r[vertex]) {
answ[0][i] = id[vertex];
}
}
}
for (int x = 1; x <= mx; x++) {
answ[x].resize(n + 1, 0);
///
answ[x][0] = ((x + 2) / 3) % 2;
///
for (int ii = 0; ii < (int)vertices[x].size(); ii++) {
int parent = vertices[x][ii].first;
int current = vertices[x][ii].second;
for (int i = l[parent]; i <= r[parent]; i++) {
if (i <= l[current]) {
if (answ[x][0] == 0) {
answ[x][i] = -1;
} else {
answ[x][i] = -2;
}
} else if (i >= r[current]) {
if (answ[x][0] == 0) {
answ[x][i] = -2;
} else {
answ[x][i] = -1;
}
} else {
if ((int)children[current].size() != 0) {
for (int j = 0; j < (int)children[current].size(); j++) {
int vertex = children[current][j];
if (i >= l[vertex] && i <= r[vertex]) {
answ[x][i] = id[vertex];
}
}
} else {
if (i == l[current]) {
if (answ[x][0] == 0) {
answ[x][i] = -1;
} else {
answ[x][i] = -2;
}
} else {
if (answ[x][0] == 0) {
answ[x][i] = -2;
} else {
answ[x][i] = -1;
}
}
}
}
}
}
}
// for (int x = 0; x <= mx; x++) {
// for (int j = 0; j <= n; j++) {
// cout << answ[x][j] << " ";
// }
// cout << endl;
// cout << endl;
// }
return answ;
}
