#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; int quanti_uguali = 0; for (int i = 0; i < 475; i ++) { auto v = ask(i); int s = v[0], d = v[1]; if (s + d == quanti) quanti_uguali ++; 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(475, N, quanti, quanti_uguali + 1, 0); return sol; }