#include <bits/stdc++.h> using namespace std; vector<vector<int>> cache; vector<int> ask(int i); vector<int> ask_(int i){ assert(0 <= i && i <cache.size()); if(cache[i][0] != -1) return cache[i]; cache[i] = ask(i); if(cache[i][0] == 0 && cache[i][1] == 0) return {}; return cache[i]; } int find_best(int n) { cache.resize(n, {-1, -1}); const int SQRT = 500; int mx_sm = 0; // per capire se è il peggiore for(int i = 0; i<min(SQRT, n); i++){ if(ask_(i).empty()) return i; mx_sm = max(mx_sm, cache[i][0]+cache[i][1]); } auto rec = [&](int l, int r, int _l, int _r, auto&& rec)->int{ if(l>r || _l>_r) return -1; int m = (l+r)/2; int m0 = (l+r)/2; for(; m <= r; m++){ if(ask_(m).empty()) return m; if(cache[m][0] + cache[m][1] == mx_sm){ int t = rec(l, m0-1, _l, cache[m][0]-(m-m0)-1, rec); // if(t != -1) return t; t = rec(m+1, r, cache[m][0], _r, rec); if(t != -1) return t; return -1; } } return rec(l, m0-1, _l, _r-(m-m0)-1, rec); // }; return rec(0, n-1, 0, mx_sm-1, rec); }