#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; // if(cur == 21) { // a[cur][] // } 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(l > r) 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 m1 = (2 * l + r) / 3; int m2 = (l + 2 * r) / 3; solve(cur, dep + 1, 1, l - 1, r + 1, l, m1, ans); solve(cur, dep + 1, 2, l - 1, r + 1, m1 + 1, m2, ans); solve(cur, dep + 1, 3, l - 1, r + 1, m2 + 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 + 2) % 6 < 3) ans[i][0] = 1; } solve(0, -1, 3, 1, n, 1, n, ans); return ans; }