| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1296721 | SamueleVid | The Big Prize (IOI17_prize) | C++20 | 0 ms | 0 KiB |
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;
}