#include "prison.h" #include<bits/stdc++.h> using namespace std; void solve (int id, int d, int p, int l1, int r1, int l, int r, vector<vector<int>> &ans) { int cur = d * 3 + p; for (int i = l; i <= r; i++) { ans[id][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 = r1; i <= r; i++) { if (ans[cur][0] == 0) ans[cur][i] = -2; else ans[cur][i] = -1; } l++, r--; if (l > r) return; if (r - l + 1 <= 2) { solve(cur, d + 1, 1, l - 1, r + 1, l, r, ans); return; } if (r - l + 1 <= 4) { int mid = l + r >> 1; solve(cur, d + 1, 1, l - 1, r + 1, l, mid, ans); solve(cur, d + 1, 2, l - 1, r + 1, mid + 1, r, ans); return; } int m1, m2; m1 = (2 * l + r) / 3; m2 = (l + 2 * r) / 3; solve(cur, d + 1, 1, l - 1, r + 1, l, m1, ans); solve(cur, d + 1, 2, l - 1, r + 1, m1 + 1, m2, ans); solve(cur, d + 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 // for (int i = 1, h = 0; i <= 20; i += 3, h ^= 1) { // ans[i][0] = ans[i + 1][0] = ans[i + 2][0] = h; + 1)); ans[0][0] = 1; for (int i = 1, h = 0; i + 2 <= 20; i += 3, h ^= 1) { ans[i][0] = ans[i + 1][0] = ans[i + 2][0] = h; } solve(0, -1, 3, 1, n, 1, n, ans); return ans; }