#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
vector<vector<int>> devise_strategy(int N) {
vector<vector<int>> ans(21, vector<int>(N + 1, 0));
vector<int> L = { 3, 3, 3, 3, 3, 2, 2, 1, 1 };
vector<pii> B = { pii(1, N) };
int board_s = 0, board_e = 0, is_a = 1;
for (int d : L) {
vector<pii> C;
for (int i = board_s; i <= board_e; ++i) {
ans[i][0] = is_a;
}
for (auto [s, e] : B) {
for (int i = board_s; i <= board_e; ++i) {
if (ans[i][s] >= 0) ans[i][s] = -1 - is_a;
if (ans[i][e] >= 0) ans[i][e] = -2 + is_a;
}
++s;
if (s >= e) continue;
int c = (e - s + d - 1) / d;
vector<int> nxt;
for (int j = s; j < e; j += c) {
nxt.push_back(j);
}
nxt.push_back(e);
for (int j = 1; j < int(nxt.size()); ++j) {
int ns = nxt[j - 1], ne = nxt[j] - 1;
C.emplace_back(ns, ne);
for (int k = ns; k <= ne; ++k) {
for (int i = board_s; i <= board_e; ++i) {
if (ans[i][k] >= 0) ans[i][k] = board_e + j;
}
}
for (int k = s - 1; k < ns; ++k) {
ans[board_e + j][k] = -2 + is_a;
}
for (int k = ne + 1; k <= e; ++k) {
ans[board_e + j][k] = -1 - is_a;
}
}
}
board_s = board_e + 1;
board_e += d;
is_a ^= 1;
B = C;
}
return ans;
}
