#include "prison.h" #include<bits/stdc++.h> using namespace std; vector<vector<int>> devise_strategy(int n) { int bl = sqrt(n) + 1; auto get = [&] (int x) { return (x - 1) / bl + 1; }; vector<vector<int>> ans(get(n) + bl + 1, vector<int>(n + 1)); ans[0][0] = 0; for (int i = 1; i <= n; i++) { ans[0][i] = get(i); } for (int i = 1; i <= get(n); i++) { ans[i][0] = 1; for (int j = 1; j <= n; j++) { if (get(j) < i) { ans[i][j] = -2; } else if (get(j) > i) { ans[i][j] = -1; } else { ans[i][j] = get(n) + (j - 1) - (get(j) - 1) * bl + 1; } } } for (int i = get(n) + 1; i <= get(n) + bl; i++) { ans[i][0] = 0; for (int j = 1; j <= n; j++) { int pos = (j - 1) - (get(j) - 1) * bl; if (i - get(n) - 1 <= pos) { ans[i][j] = -2; } else { ans[i][j] = -1; } } } return ans; }