#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;
}
