Tieni aggiornato il catalogo (Algobadge) 50/100

Aiuto
1

Salve, sto provando a risolvere il problema “Tieni aggiornato il catalogo”, il codice è molto facile, ma nonostante questo ottengo solo 50/100 punti per Execution timed out, qualche consiglio per ottimizzarlo?

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

vector<long long int> v;
void aggiungi(long long int id) {
    v.push_back(id);
}

void togli(long long int id) {
    v.erase(find(v.begin(), v.end(), id));
}

int conta(long long int id) {
        return count(v.begin(), v.end(), id);
}
2

Ci sono vari topic a riguardo ad esempio Catalogo Compilazione Fallita

3

Ciao, io sto facendo lo stesso problema (catalogo) e penso di aver trovato una soluzione, ma ottengo 50/100 perché il case 029 e 031 hanno il risultato sbagliato.

Sto usando ‘map’ perché mi sembra la struttura di dati più adeguata, essendo che posso accedere agli elementi senza l’utilizzo di cicli vari; se usavo un vettore avrei dovuto fare una ricerca lineare ogni volta che cercavo di accedere agli scaffali.

Qui il codice:

using namespace std;
#include <iostream>
#include <map>

map <int, int> M;

void aggiungi(long long int id) {
	if (M[id] == 0) M[id] = 1;
	else M[id]++;
	// M[id] = M[id] == 0 ? 1 : M[id] + 1;
}

void togli(long long int id) {
	M[id] = M[id] - 1;
}

int conta(long long int id) {
	return M[id];
}
4

Stai usando una mappa con int (32 bit) quando il tipo del problema e’ long long int (64 bit) (in c++ non ti da warning a meno che non abiliti -Wconversion)

5

La std::map è una buona idea, ma non ci serve avere la struttura ordinata, sarebbe più adatta una std::unordered_map. Queste sono solo piccolezze, comunque il problema era l’overflow.
Se ti interessa, anche nelle mappe puoi usare gli operatori ++ e --: se non esiste nessun elemento alla chiave id con il ++ viene aggiunto con valore 1. Poi per il -- è garantito che non devi togliere da nessuno scaffale vuoto e in questo caso il problema non si pone.

6

Grazie mille! Dovrei stare più attento alle istruzioni del problema la prossima volta

7

Grazie! Alla fine ho usato la std::map perché era la prima struttura dati che mi era venuta in mente; avevo provato ad utilizzare la std::unordered_map, ma mi dava problemi con la compilazione e non avevo voglia di rifare il codice anche se corto :P.
Grazie anche per il ++ e il --, lo terrò da conto la prossima volta che userò il C++

1 Mi Piace