#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_esterni, int quanti_dx_esterni) { // 1. Condizioni di terminazione if (sol != -1 || l >= r) return; if (dentro == 0) return; // 2. Caso Base: segmento di un solo elemento if (r - l == 1) { sol = l; return; } // 3. Query singola (Ricerca Binaria) int m = l + (r - l) / 2; auto v = ask(m); int s_assoluto = v[0]; // Premi più costosi a sinistra di m int d_assoluto = v[1]; // Premi più costosi a destra di m // 4. Diamante Trovato if (s_assoluto + d_assoluto == 0) { sol = m; return; } // 5. Normalizzazione: calcola i conteggi 'dentro' il segmento int s_dentro = s_assoluto - quanti_sx_esterni; int d_dentro = d_assoluto - quanti_dx_esterni; // Controlliamo se 'm' è un premio di riferimento (es. lecca-lecca) if (s_assoluto + d_assoluto == quanti_non_brutti) { // Se 'm' è un lecca-lecca, usiamo i suoi conteggi per restringere la ricerca. // I premi più costosi sono quelli a sinistra (s_dentro) e a destra (d_dentro) di 'm'. // Ricerca nel segmento sinistro: [l, m) rec(l, m, s_dentro, quanti_sx_esterni, quanti_dx_esterni + d_dentro); // Ricerca nel segmento destro: [m + 1, r) rec(m + 1, r, d_dentro, quanti_sx_esterni + s_dentro, quanti_dx_esterni); } else { // Se 'm' NON è un lecca-lecca (è un premio più costoso), // la soluzione deve trovarsi in uno dei due segmenti. // La logica standard IOI è: il diamante non si può trovare dove ci sono // già stati trovati premi più costosi di 'm'. // Qui, per semplicità, si cerca il diamante che ha s+d=0. // La logica del problema suggerisce di dividere semplicemente l'intervallo // in base al conteggio 'dentro' (il numero di premi più costosi). // Se s_dentro > 0, il segmento sinistro contiene ancora un premio costoso. if (s_dentro > 0) { rec(l, m, s_dentro, quanti_sx_esterni, quanti_dx_esterni + d_dentro); } // Se d_dentro > 0, il segmento destro contiene ancora un premio costoso. if (d_dentro > 0) { rec(m + 1, r, d_dentro, quanti_sx_esterni + s_dentro, quanti_dx_esterni); } } } int find_best(int N) { // Il codice di pre-ricerca è ragionevole, ma: // 1. Usa 473 (che è un numero specifico). Lo standard IOI usa 474 o 500. // Lasciamo 473, ma in un contesto reale andrebbe adattato. // 2. 'quanti_uguali' è un conteggio dei lecca-lecca tra 0 e 472. int quanti = 0; // Il massimo s+d trovato (corrisponde al lecca-lecca) int quanti_uguali = 0; // Numero di lecca-lecca trovati tra 0 e 472 int ziopera = -1; // Indice del primo lecca-lecca (non usato direttamente, ma utile) for (int i = 0; i < 473; i ++) { auto v = ask(i); int s = v[0], d = v[1]; if (s + d > quanti) { quanti = s + d; ziopera = i; quanti_uguali = 1; // Un nuovo massimo, resetta il conteggio a 1 } else if (s + d == quanti) { quanti_uguali ++; // Trovato un altro premio di riferimento } if (s + d == 0) return i; // Trovato subito il diamante } quanti_non_brutti = quanti; // Richiama la ricorsione solo sull'intervallo [473, N). // quanti: il numero totale di premi costosi ancora "dentro" l'intervallo totale. // quanti_uguali: il numero di lecca-lecca trovati nel segmento esterno [0, 472]. // L'algoritmo IOI corretto usa quanti_uguali come conteggio dei premi più costosi (non-lecca-lecca). // Qui si assume che i parametri siano: (l, r, premi_costosi_dentro, premi_costosi_sx_esterni, premi_costosi_dx_esterni) // Assumendo che 'quanti' sia il numero totale di premi costosi (non-lecca-lecca) in tutta la riga N, // e che i lecca-lecca non siano mai contati: // Dentro: quanti (tutti i non-lecca-lecca non ancora trovati) - (premi costosi trovati in [0, 472]) // Premi costosi trovati in [0, 472] = 473 - quanti_uguali int premi_costosi_in_esterni = (473 - quanti_uguali); int dentro_segmento_iniziale = quanti - premi_costosi_in_esterni; rec(473, N, dentro_segmento_iniziale, premi_costosi_in_esterni, 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; // }