#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
int idx[30][4];
vector<vector<int>> f;
void dnc(int pId, int stage, int rank, int pL, int pR, int l, int r) {
int id = idx[stage][rank];
f[id][0] = (stage & 1);
for (int i = l; i <= r; ++i) f[pId][i] = id;
for (int i = pL; i <= l; ++i) f[id][i] = -f[id][0] - 1;
for (int i = r; i <= pR; ++i) f[id][i] = -2 + f[id][0];
if (r - l - 1 <= 0) return;
if (r - l - 1 <= 2) {
dnc(id, stage + 1, 1, l, r, l + 1, r - 1);
return;
}
if (r - l - 1 <= 4) {
int sz = (r - l - 2) / 2 + 1;
dnc(id, stage + 1, 1, l, r, l + 1, l + sz);
dnc(id, stage + 1, 2, l, r, l + sz + 1, r - 1);
return;
}
int sz = (r - l - 2) / 3 + 1;
dnc(id, stage + 1, 1, l, r, l + 1, l + sz);
dnc(id, stage + 1, 2, l, r, l + sz + 1, r - sz - 1);
dnc(id, stage + 1, 3, l, r, r - sz, r - 1);
}
vector<vector<int>> devise_strategy(int N) {
f.assign(21, vector<int>(N + 1));
for (int i = 1, num = 0; i <= 7; ++i) {
for (int j = 1; j <= 3; ++j) idx[i][j] = ++num;
}
dnc(0, 0, 0, 1, N, 1, N);
return f;
}
