Soste in autostrada (Autogrill)

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.

Spero la spiegazione sia comprensibile.

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().

Grazie mille! Funziona perfettamente!

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