Ciao a tutti, non riesco a capire perché quando invio i primi due subtask l’output è corretto, mentre per tutti gli altri non funziona… grazie in anticipo!
#include <iostream>
#include <set>
using namespace std;
void inizia() { }
set<long long> autogrillaperti;
void apri(long long p) {
autogrillaperti.insert(p);
}
void chiudi(long long p) {
autogrillaperti.erase(p);
}
long long chiedi(long long p) {
if (autogrillaperti.empty())
return -1;
auto numeroappenamaggiore = autogrillaperti.lower_bound(p);
auto numeroappenaminore = autogrillaperti.upper_bound(p);
if (*numeroappenamaggiore == p)
return p;
else if (*numeroappenaminore == p)
return p;
long long distanzaconmaggiore = *numeroappenamaggiore - p;
long long distanzaconminore = *numeroappenaminore - p;
if (distanzaconminore < distanzaconmaggiore)
return *numeroappenaminore;
else if (distanzaconmaggiore < distanzaconminore)
return *numeroappenamaggiore;
else
return *numeroappenamaggiore;
}
Ci sono un po’ di errori, il più importante è che upper_bound non restituisce il numero appena minore.
Funziona in maniera molto simile a lower_bound, solamente restituisce il primo elemento maggiore di p mentre lower_bound restituisce il primo maggiore o uguale. Quindi basta chiamare una fra le due funzioni per trovare l’elemento subito maggiore.
Per trovare l’elemento subito minore invece basta utilizzare la funzione prev: dato un iteratore come quelli restituiti da lower_bound, restituisce un’iteratore all’elemento precedente. In particolare, in questo caso l’elemento precedente all’elemento subito sopra è proprio l’elemento subito sotto.
Ci sono altri due errori:
Gli iteratori non sempre sono validi. In particolare se non esiste nessun elemento maggiore di p o nessun elemento minore di p otterrai degli iteratori invalidi. Su questo sito sito puoi trovare maggiori dettagli sugli iteratori (oppure cerca su stackoverflow / google, se ti serve aiuto chiedi ulteriori info qua)
TI stai dimenticando di una cosa quando fai le sottrazioni.
Ho provato a correggere alcuni errori, passa 5 test, gli altri no.
#include <iostream>
#include <set>
using namespace std;
void inizia() { }
set<long long> autogrillaperti;
void apri(long long p) {
autogrillaperti.insert(p);
}
void chiudi(long long p) {
autogrillaperti.erase(p);
}
long long chiedi(long long p) {
if (autogrillaperti.empty())
return -1;
auto numeroappenamaggiore = autogrillaperti.lower_bound(p);
auto numeroappenaminore = numeroappenamaggiore;
if (autogrillaperti.size() > 1)
numeroappenaminore = prev(numeroappenamaggiore);
long long distanzaconmaggiore = *numeroappenamaggiore - p;
long long distanzaconminore = p - *numeroappenaminore;
if (distanzaconminore < distanzaconmaggiore)
return *numeroappenaminore;
else if (distanzaconmaggiore < distanzaconminore)
return *numeroappenamaggiore;
else
return *numeroappenamaggiore;
}
Mancano ancora i check sulla validità degli iteratori:
non stai controllando che esista il lower bound
autogrillaperti.size() > 1 non fa la cosa guista:
– Potrebbe esserci un solo autogrill, che però è proprio quello che stai cercando.
– Potrebbero esserci più autogrill, però il lower_bound è già il primo di tutti e non c’è nulla prima.
Il modo giusto per fare i controlli è confrontare gli iteratori con autogrillaperti.begin() ed autogrillaperti.end().
#include <iostream>
#include <set>
using namespace std;
void inizia() { }
set<long long> autogrillaperti;
void apri(long long p) {
autogrillaperti.insert(p);
}
void chiudi(long long p) {
autogrillaperti.erase(p);
}
long long chiedi(long long p) {
if (autogrillaperti.empty())
return -1;
auto numerovicino = autogrillaperti.lower_bound(p);
if (numerovicino == autogrillaperti.end()) return *autogrillaperti.rbegin();
if (numerovicino == autogrillaperti.begin()) return *numerovicino;
if (autogrillaperti.size() == 1) return *numerovicino;
if (*numerovicino == p) return *numerovicino;
long long numeromaggiore = *numerovicino;
long long numerominore = *prev(numerovicino);
if (numeromaggiore - p <= p - numerominore)
return numeromaggiore;
else
return numerominore;
}