#include "prison.h" #include <bits/stdc++.h> using namespace std; void solve(int x, int dep, int whi, int l1, int r1, int l, int r, vector<vector<int> >& ans){ int cur = dep * 3 + whi; for(int i = l; i <= r; i++) ans[x][i] = cur; for(int i = l1; i <= l; i++){ if(ans[cur][0] == 0) ans[cur][i] = -1; else ans[cur][i] = -2; } for(int i = r; i <= r1; i++){ if(ans[cur][0] == 0) ans[cur][i] = -2; else ans[cur][i] = -1; } l++; r--; if(r - l < 0) return; if (r - l < 2) { solve(cur, dep + 1, 1, l - 1, r + 1, l, r, ans); return; } if (r - l < 4) { int mid = (l + r) / 2; solve(cur, dep + 1, 1, l - 1, r + 1, l, mid, ans); solve(cur, dep + 1, 2, l - 1, r + 1, mid + 1, r, ans); return; } int len = (r - l) / 3; solve(cur, dep + 1, 1, l - 1, r + 1, l, l + len, ans); solve(cur, dep + 1, 2, l - 1, r + 1, l + len + 1, r - len, ans); solve(cur, dep + 1, 3, l - 1, r + 1, r - len + 1, r, ans); } vector<vector<int>> devise_strategy(int n) { vector<vector<int> > ans(21, vector<int> (n + 1, 0)); for(int i = 0; i <= 20; i++){ if(i % 6 < 3) ans[i][0] = 1; } solve(0, -1, 3, 1, n, 1, n, ans); return ans; }