#include <iostream> #include <vector> #include <algorithm> using namespace std; static const int max_q = 10000; static int n; static int query_count = 0; static vector<int> g; static vector<vector<int> > rank_count; vector<int> ask(int i); // vector<int> ask(int i) { // query_count++; // if(query_count > max_q) { // cerr << "Query limit exceeded" << endl; // exit(0); // } // if(i < 0 || i >= n) { // cerr << "Bad index: " << i << endl; // exit(0); // } // vector<int> res(2); // res[0] = rank_count[g[i] - 1][i + 1]; // res[1] = rank_count[g[i] - 1][n] - res[0]; // return res; // } int quanti_non_brutti; int sol = -1; void rec(int l, int r, int dentro, int quanti_sx, int quanti_dx) { if (r - l == 0) return; if (dentro == 0) return; int m = (l + r) / 2; for (int k = m; k < r; k ++) { auto v = ask(k); int s = v[0], d = v[1]; if (s + d == 0) { sol = k; return; } if (s + d != quanti_non_brutti) { continue; } s -= quanti_sx; d -= quanti_dx; rec(l, m, s, quanti_sx, quanti_dx + d); rec(k + 1, r, d, s + quanti_sx, quanti_dx); return; } rec(l, m, dentro, quanti_sx, quanti_dx); } int find_best(int N) { int quanti = 0; int ziopera; for (int i = 0; i < 500; i ++) { auto v = ask(i); int s = v[0], d = v[1]; if (s + d > quanti) { quanti = s + d; ziopera = i; } if (s + d == 0) return i; } quanti_non_brutti = quanti; // cout << "quanti_non_brutti : " << quanti_non_brutti << '\n'; // cout << "primo lombrico : " << ziopera << '\n'; rec(0, N, quanti, 0, 0); return sol; } // int main() { // cin >> n; // g.resize(n); // for(int i = 0; i < n; i++) { // cin >> g[i]; // if(g[i] < 1) { // cerr << "Invalid rank " << g[i] << " at index " << i << endl; // exit(0); // } // } // int max_rank = *max_element(g.begin(), g.end()); // rank_count.resize(max_rank + 1, vector<int>(n + 1, 0)); // for(int r = 0; r <= max_rank; r++) { // for(int i = 1; i <= n; i++) { // rank_count[r][i] = rank_count[r][i - 1]; // if(g[i - 1] == r) // rank_count[r][i]++; // } // } // for(int i = 0; i <= n; i++) // for(int r = 1; r <= max_rank; r++) // rank_count[r][i] += rank_count[r - 1][i]; // int res = find_best(n); // cout << res << endl << "Query count: " << query_count << endl; // return 0; // }