#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_best2(int n, vector<int> &idx) { // cache.resize(n, {-1, -1}); const int SQRT = 30; int mx_sm = 0; // per capire se è il peggiore int l2_ = 0; for(int i = 0; i<min(SQRT, n); i++){ if(ask_(idx[i]).empty()) return idx[i]; if(mx_sm < cache[idx[i]][0]+cache[idx[i]][1]){ l2_ = cache[idx[i]][0]; mx_sm = cache[idx[i]][0]+cache[idx[i]][1]; } else if(mx_sm > cache[idx[i]][0]+cache[idx[i]][1]) l2_++; } 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_(idx[m]).empty()) return idx[m]; if(cache[idx[m]][0] + cache[idx[m]][1] == mx_sm){ int t = rec(l, m0-1, _l, cache[idx[m]][0]-(m-m0)-1, rec); // if(t != -1) return t; t = rec(m+1, r, cache[idx[m]][0], _r, rec); if(t != -1) return t; return -1; } } return rec(l, m0-1, _l, _r-(m-m0), rec); // }; return rec(SQRT, n-1, l2_, mx_sm-1, rec); } int find_best(int n) { cache.resize(n, {-1, -1}); const int SQRT = 500; int mx_sm = 0; // per capire se è il peggiore int l2_ = 0; for(int i = 0; i<min(SQRT, n); i++){ if(ask_(i).empty()) return i; if(mx_sm < cache[i][0]+cache[i][1]){ l2_ = cache[i][0]; mx_sm = cache[i][0]+cache[i][1]; } else if(mx_sm > cache[i][0]+cache[i][1]) l2_++; } vector<int> idx; for(int i = 0; i<min(SQRT, n); i++){ if(mx_sm > cache[i][0]+cache[i][1]) idx.push_back(i); } auto rec = [&](int l, int r, int _l, int _r, auto&& rec)->int{ if(l>r || _l>_r) return -1; if(r-l == _r-_l){ for(int i = l; i<=r; i++) idx.push_back(i); 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; } else idx.push_back(m); } return rec(l, m0-1, _l, _r-(m-m0), rec); // }; int t = rec(SQRT, n-1, l2_, mx_sm-1, rec); if(t != -1) return t; sort(idx.begin(), idx.end()); return find_best2(idx.size(), idx); assert(0); }