#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
struct seg {
pair<int, int> old, cur;
};
vector<vector<int>> devise_strategy(int N) {
vector<vector<int>> vvi;
vector<vector<seg>> help;
help.push_back(vector<seg>());
vector<seg> vs;
seg tmp;
tmp.old = {1, N};
vvi.push_back(vector<int>(N + 1));
vvi[0][0] = 0;
for (int i = tmp.old.first; i >= 1; i--) vvi[0][i] = -1;
for (int i = tmp.old.second; i <= N; i++) vvi[0][i] = -2;
tmp.cur = {2, (N + 1) / 2};
for (int i = tmp.cur.first; i <= tmp.cur.second; i++) vvi[0][i] = 1;
vs.push_back(tmp);
help.push_back(vs);
vs.clear();
tmp.cur = {(N + 1) / 2 + 1, N - 1};
for (int i = tmp.cur.first; i <= tmp.cur.second; i++) vvi[0][i] = 2;
vs.push_back(tmp);
help.push_back(vs);
for (int i = 1; 1; i += 2) {
do {
vvi.push_back(vector<int>(N + 1));
if(i%4==1)
vvi[i][0] = 1;
vector<seg> vsg;
for (auto a : help[i]) {
for (int j = a.cur.first; j >= a.old.first; j--) {
if (i % 4 == 1)
vvi[i][j] = -2;
else
vvi[i][j] = -1;
}
for (int j = a.cur.second; j <= a.old.second; j++) {
if (i % 4 == 1)
vvi[i][j] = -1;
else
vvi[i][j] = -2;
}
seg tmp;
tmp.old = a.cur;
tmp.cur = {tmp.old.first + 1, (tmp.old.first + tmp.old.second) / 2};
vsg.push_back(tmp);
tmp.cur = {(tmp.old.first + tmp.old.second) / 2 + 1,
tmp.old.second - 1};
vsg.push_back(tmp);
for (int j = tmp.old.first + 1;
j <= (tmp.old.first + tmp.old.second) / 2; j++)
vvi[i][j] = i + 2;
for (int j = (tmp.old.first + tmp.old.second) / 2 + 1;
j <= tmp.old.second - 1; j++)
vvi[i][j] = i + 3;
}
help.push_back(vsg);
i++;
} while (i % 2 == 0);
i -= 2;
for (int j = 0; j <= N; j++)
if (vvi[i][j] > 0 || vvi[i + 1][j] > 0) goto A;
return vvi;
A:;
}
}
