#include <vector> #include <cmath> #include <cstring> #include "prize.h" // Funzione interattiva 'ask()' #define X first #define Y second using namespace std; // Definizione di un alias per coppia di interi (per i risultati della query) typedef pair<int, int> pii; // Variabile globale che memorizza il massimo valore s+d trovato finora. // Questo valore identifica il premio Meno Costoso (Lecca-Lecca), // poiché ha il conteggio massimo di tutti gli altri premi più costosi. int numb; // Array per memorizzare i risultati delle query (memoization). // 210000 è scelto per coprire N=200000. pii P[210000]; // Array booleano per tenere traccia delle scatole già interrogate. bool mark[210000]; // Vettore temporaneo per memorizzare il risultato della funzione ask(). vector<int> vtmp; /** * Funzione per interrogare una scatola. Utilizza la memoization. * @param x: Indice della scatola da interrogare. * @return pii: Coppia (premi_più_costosi_a_sx, premi_più_costosi_a_dx). */ pii query(int x) { // 1. Memoization: se la scatola è già stata interrogata, restituisce il risultato memorizzato. if (mark[x]) return P[x]; // 2. Esecuzione della query interattiva. mark[x] = true; vtmp = ask(x); pii tmp = pii(vtmp[0], vtmp[1]); // 3. Condizione di Trovato (Diamante): se s + d = 0, è il diamante. // L'uso di 'throw x' è una tecnica comune in programmazione competitiva // per uscire immediatamente dalla ricorsione e restituire la risposta. if (tmp.X + tmp.Y == 0) throw x; // 4. Memorizzazione del risultato e ritorno. return P[x] = tmp; } /** * Funzione di Ricerca Binaria Adattiva. * Cerca un premio di riferimento (Lecca-Lecca) in un intervallo per eliminare segmenti. * * @param l: Limite sinistro dell'intervallo di ricerca. * @param r: Limite destro dell'intervallo di ricerca. * @param nl: Conteggio dei premi COSTOSI già identificati nell'intervallo ESTERNO SINISTRO ([0, l-1]). * @param nr: Conteggio dei premi COSTOSI già identificati nell'intervallo ESTERNO DESTRO ([r+1, N-1]). */ void bs(int l, int r, int nl, int nr) { if (l > r) return; // Scansione Adattiva attorno al punto medio: // Questo loop NON è una scansione lineare inefficiente. È un modo // elegante per eseguire query in una sequenza simile a [m, m-1, m+1, m-2, m+2, ...] // attorno al punto centrale, al fine di trovare rapidamente una scatola di riferimento. for (int i = 0; i <= r - l; i++) { int midl = (l + r) / 2 - i / 2; int midr = (l + r) / 2 + (i + 1) / 2; int mid; // Alterna la scatola da interrogare tra midl e midr per "allargarsi" dal centro. if (i % 2 == 0) mid = midl; else mid = midr; pii tmp = query(mid); // La condizione chiave: Trovato un premio di Riferimento (Lecca-Lecca) // Se s + d è uguale al massimo conteggio 'numb', allora 'mid' è un lecca-lecca. if (tmp.X + tmp.Y == numb) { // 1. Calcolo dell'influenza del segmento di scarto: // Questa parte calcola quanti premi costosi si trovano nell'area // tra midl e midr (se fosse stata interrogata solo midl o solo midr). int tmpl = (i % 2 == 0 ? 0 : midr - midl); // (solo se mid = midr) int tmpr = (i % 2 == 1 ? 0 : midr - midl); // (solo se mid = midl) // 2. Suddivisione Ricorsiva ed Eliminazione: // Calcola i premi costosi nel segmento sinistro [l, midl-1]. // I premi costosi 'dentro' sono: (tmp.X - premi_costosi_nel_segmento_di_scarto) // Se questo valore è maggiore di 'nl' (premi costosi esterni a sinistra), // significa che ci sono ancora premi costosi da trovare a sinistra. if (tmp.X - tmpl > nl) // Il nuovo nr è: nr precedente + premi_costosi_che_ho_lasciato_a_destra (tmp.Y + tmpl) bs(l, midl - 1, nl, tmp.Y + tmpl); // Calcola i premi costosi nel segmento destro [midr+1, r]. // Stessa logica per la parte destra: se il conteggio normalizzato // è maggiore di 'nr' (premi costosi esterni a destra). if (tmp.Y - tmpr > nr) // Il nuovo nl è: nl precedente + premi_costosi_che_ho_lasciato_a_sinistra (tmp.X + tmpr) bs(midr + 1, r, tmp.X + tmpr, nr); // Trovato il punto di riferimento, abbiamo diviso il problema. Usciamo dal loop. break; } } } /** * Funzione principale per trovare il diamante. * @param n: Dimensione totale della riga. * @return int: Indice del diamante. */ int find_best(int n) { if (n == 1) return 0; // Usa un blocco try-catch per catturare il 'throw x' quando il diamante è trovato. try { numb = 0; // Inizializza i flag di memoization memset(mark, false, sizeof mark); int p = 0; // Fase 1: Pre-ricerca del Lecca-Lecca (Premio di Riferimento) // Esegue O(sqrt(n)) query iniziali. (475 per N=200000). // Cerca il massimo valore di s+d (numb) per identificare il lecca-lecca. for (int i = 0; i < sqrt(n) + 30 && i < n && numb <= 26; i++) { pii tmp = query(i); if (tmp.X + tmp.Y > numb) p = i; // p è l'indice del lecca-lecca (o un premio vicino) numb = max(numb, tmp.X + tmp.Y); } // Fase 2: Ricerca Binaria sul resto della riga. // Inizia la ricerca binaria dal lecca-lecca 'p' fino alla fine 'n-1'. // I parametri nl=p e nr=0 indicano che 'p' scatole sono a sinistra, // ma si sta lavorando sull'intervallo [p, n-1]. // La gestione dei parametri 'nl' e 'nr' qui è sottile e varia a seconda dell'implementazione. bs(p, n - 1, p, 0); } catch (int ans) { // Cattura l'indice del diamante lanciato da query() return ans; } // Se la ricerca fallisce (non dovrebbe), restituisce -1. return -1; }