#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
#define vec vector
vec<int> ids;
vec<bool> processed;
map<int, vec<int>> arrs;
int bits = 13;
int get_terminate(int x) {
if (x == 0) {
return -1;
}
return -2;
}
void gen_last(int N, int id, int bag, bool on) {
if (processed[id]) return;
vec<int> arr(N+1, 0);
for (int i = 1; i <= N; i++) {
if (i & 1) {
if (!on) {
arr[i] = get_terminate(1 - bag);
}
} else {
if (on) {
arr[i] = get_terminate(bag);
}
}
}
processed[id] = 1;
arrs[id] = arr;
}
void gen(int N, int id, int next_on, int next_off, int bag, int bit, bool on) {
if (processed[id]) {
return;
}
vec<int> procedure(N+1, 0);
procedure[0] = bag;
for (int i = 1; i <= N; i++) {
if ((1 << (bit+1)) & i) {
// bit on
if (on) {
// continue
procedure[i] = ((1 << (bit)) & i) ? next_on : next_off;
} else {
// terminate (other min)
procedure[i] = get_terminate(1 - bag);
}
} else {
// bit off
if (on) {
// terminate (this min)
procedure[i] = get_terminate(bag);
} else {
// continue
procedure[i] = ((1 << (bit)) & i) ? next_on : next_off;;
}
}
}
arrs[id] = procedure;
processed[id] = 1;
if (bit > 0) {
int foward_on = ids.back(); ids.pop_back();
int foward_off = ids.back(); ids.pop_back();
gen(N, next_on, foward_on, foward_off, 1 - bag, bit - 1, 1);
gen(N, next_off, foward_on, foward_off, 1 - bag, bit - 1, 0);
}
if (bit == 0) {
gen_last(N, next_on, 1 - bag, 1);
gen_last(N, next_off, 1 - bag, 0);
}
}
std::vector<std::vector<int>> devise_strategy(int N) {
ids.resize(500);
processed.assign(500, 0);
iota(ids.begin(), ids.end(), 0);
reverse(ids.begin(), ids.end());
ids.pop_back();
int next_on = ids.back(); ids.pop_back();
int next_off = ids.back(); ids.pop_back();
vec<int> first(N+1, 0);
for (int i = 1; i <= N; i++) {
if ((1 << bits) & i) {
first[i] = next_on;
} else {
first[i] = next_off;
}
}
arrs[0] = first;
processed[0] = 1;
int foward_on = ids.back(); ids.pop_back();
int foward_off = ids.back(); ids.pop_back();
gen(N, next_on, foward_on, foward_off, 1, bits - 1, 1);
gen(N, next_off, foward_on, foward_off, 1, bits - 1, 0);
vec<vec<int>> procedure(arrs.size());
for (auto [i, v] : arrs) {
procedure[i] = v;
}
/*
for (auto v : procedure) {
for (int i = 0; i <= N; i++) {
cout << v[i] << " ";
}
cout << endl;
}
*/
return procedure;
}
