Aiuto con Soste in autostrada (autogrill)

Aiuto
1

Buongiorno a tutti. Sto provando a risolvere il problema Soste in autostrada (autogrill) da un po’ oramai ma per ora mi funzionano solo i primi 2 casi e 2 del secondo subtask.
Questo è il mio codice:

#include <set>

using namespace std;

set<int> AG;

void inizia() {
    return;
}

void apri(long long p) {
    AG.insert(p);
    return;
}

void chiudi(long long p) {
    AG.erase(p);
    return;
}

long long chiedi(long long p) {
    if(AG.empty())
        return -1;
    auto NearestPos = AG.lower_bound(p);
    if(AG.size() == 1 || NearestPos == AG.end() || NearestPos == AG.begin())
        return *NearestPos;
    if (*NearestPos == p)
        return *NearestPos;
    
    long long leftNearest = *prev(NearestPos);
    long long rightNearest = *NearestPos;
    if (p - leftNearest >= rightNearest - p)
        return rightNearest;
    return leftNearest;

}

Qualcuno riesce a trovare l’errore?
Grazie in anticipo

2

Dovresti rivedere un po’ i casi degeneri:
Intanto, se NearestPos == AG.end() non poi restituire quel valore perché non esiste.
Poi se AG.size() == 1 non è detto che quell’elemento sia puntato da NearestPos (non è detto che sia \geq p)

3

Grazie, pensavo che AG.end() si riferisse all’ultimo elemento del set come avevo letto online, e che non sono ancora molto esperto con il C++, allora come posso vedere l’ultimo elemento del set?

4

Nei std::set come anche in tutte la STL, .end() punta alla posizione subito dopo l’ultimo elemento.
Se ad esempio hai un vector<int> A = {1,2,3,4} , A.end() punterà subito dopo il 4, quindi prev(A.end()) puterà al 4.
Esistono, e sono molto comodi, i reverse iterator.
A.rbegin() punta a 4 e A.rend() punta alla posizione subito prima di 1.
Nel tuo caso AG.rbegin() punta all’ultimo elemento di AG

5

Ok, grazie mille, proverò con AG.rend()

6 
#include <set>

using namespace std;

set<int> AG;

void inizia() {
    return;
}

void apri(long long p) {
    AG.insert(p);
    return;
}

void chiudi(long long p) {
    AG.erase(p);
    return;
}

long long chiedi(long long p) {
    if(AG.empty())
        return -1;
    auto NearestPos = AG.lower_bound(p);
    if (NearestPos == AG.end())
        return *AG.rbegin();
    if (NearestPos == AG.begin())
        return *NearestPos;
    if(AG.size() == 1) 
        return *NearestPos;
    if (*NearestPos == p)
        return *NearestPos;
    
    long long leftNearest = *prev(NearestPos);
    long long rightNearest = *NearestPos;
    if (p - leftNearest >= rightNearest - p)
        return rightNearest;
    return leftNearest;

}

Usando AG.rbegin() Va molto meglio ma ancora non li risolve tutti
Non capisco proprio cosa altro potrei fare
Grazie ancora per l’aiuto

7

Controlla il tipo di dato del set

2 Mi Piace
8

Non ci credo. Grazie mille!
Ora 100/100

1 Mi Piace