#include <bits/stdc++.h>
#include "prison.h"
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> ii;
#define FOR(i,a,b) for(int i=(a); i<(b); ++i)
#define ROF(i,a,b) for(int i=(b)-1; i>=(a); --i)
#define all(v) begin(v),end(v)
#define pb push_back
//offline dp results
//{5000, 1666, 832, 277, 92, 30, 14, 6, 2}
//{0, 3, 5, 8, 11, 14, 16, 18, 20}
std::vector<std::vector<int>> devise_strategy(int N) {
vi layers{0, 3, 5, 8, 11, 14, 16, 18, 20};
vi splitIntoTwo{1,2,3,12,13,14,15,16,17,18};
vi splitIntoThree{0,4,5,6,7,8,9,10,11};
vector<bool> checkLeft(21);
vector<vector<ii>> intervals(21);
vector<vector<ii>> parInterval(21); //interval of the previous step. indexed the same way as intervals;
intervals[0].pb({1,5000});
parInterval[0].pb({1,5000});
checkLeft[0] = true;
FOR(i,0,19) {
for(auto [l,r]: intervals[i]) {
int d = r-l;
int t = *next(lower_bound(all(layers),i));
if(binary_search(all(splitIntoTwo),i)) {
int mid = l + d/2;
intervals[t-1].pb({l+1,mid});
intervals[t].pb({mid+1,r-1});
parInterval[t-1].pb({l,r});
parInterval[t].pb({l,r});
checkLeft[t-1] = checkLeft[t] = !checkLeft[i];
}
if(binary_search(all(splitIntoThree),i)) {
int mid0 = l + (d+1)/3, mid1 = l + 2*((d+1)/3);
intervals[t-2].pb({l+1,mid0});
intervals[t-1].pb({mid0+1,mid1});
intervals[t].pb({mid1+1,r-1});
parInterval[t-2].pb({l,r});
parInterval[t-1].pb({l,r});
parInterval[t].pb({l,r});
checkLeft[t-2] = checkLeft[t-1] = checkLeft[t] = !checkLeft[i];
}
}
}
vector<vi> strat(21,vi(N+1));
FOR(i,0,21) {
strat[i][0] = (checkLeft[i]?0:1);
FOR(j,1,N+1) {
int l = 0, r = N+1;
FOR(k,0,int(intervals[i].size())) {
if(parInterval[i][k].first <= j && j <= parInterval[i][k].second) {
l = intervals[i][k].first;
r = intervals[i][k].second;
break;
}
}
if(j <= l) strat[i][j] = (checkLeft[i]?-1:-2);
else if(j >= r) strat[i][j] = (checkLeft[i]?-2:-1);
else if(binary_search(all(splitIntoTwo),i)) {
int t = *next(lower_bound(all(layers),i));
FOR(k,0,2) for(auto [f,s]: intervals[t-k]) if(f <= j && j <= s) strat[i][j] = t-k;
} else if(binary_search(all(splitIntoThree),i)) {
int t = *next(lower_bound(all(layers),i));
FOR(k,0,3) for(auto [f,s]: intervals[t-k]) if(f <= j && j <= s) strat[i][j] = t-k;
} else {
strat[i][j] = 0; //never used
}
assert(strat[i][j] >= -2 && strat[i][j] <= 20);
}
}
return strat;
}
