Problema catalogo help

include <bits/stdc++.h>
vector<pair<int, int>> a;

void aggiungi(long long int id) {
	int j;
	if(a.size()==0) a.push_back(make_pair(id, 1));
	else{
	    for(int j=0; j<a.size(); j++){
	    	if(a[j].first==id){        
			a[j].second++; 
			break;
			}         
	    	else if(j==(a.size()-1)) a.push_back(make_pair(id, 1));
		}
	}
}

void togli(long long int id) {
    for(int i=0; i<a.size(); i++){
    	if(a[i].first==id)
			a[i].second--;
    	else if(a[i].second==0) a.erase(a.begin() + i);
			
	}
}

int conta(long long int id) {
	for(int i=0; i<a.size(); i++){
		if(a[i].first==id) return a[i].second;
	}
	return 0;
}

Salve a tutti, sono nuovo nel forum, sto trovando difficoltà con questo problema perché non mi da i risultati aspettati, se non in alcuni casi specifici (secondo il mio ragionamento però dovrebbe funzionare sempre ma sicuramente sbaglio); se poi mi potete dare anche un piccolo hint per renderlo migliore sono ben aperto.
(Sto facendo lettura e scrittura su file/ terminale perché pur capendo come funzionano i grader non so eseguirli (solitamente uso dev C++ o Visual Studio Code))

ciao!
inanzitutto attenzione alle assunzioni, ogni id è <= di 10^18, perciò un intero non basta per memorizzarlo, hai bisogno dei long long.
leggendo il tuo codice ho notato che nella funzione aggiungi con la riga

fai push_back nel vettore del nuovo valore, ma poi con il successivo giro del for lo visiti, incrementandolo a 2.
la funzione size ricalcola ogni volta la dimensione del vettore, perciò dopo che fai un push_back la size aumenterà di 1 e j visiterà anche quel valore che hai appena aggiunto, incrementandolo a 2.

con queste accortezze arrivi a 50 punti, perchèl’ultimo subtask ti andrà fuori tempo.
per risolvere anche quello ti do solo un hint:
il tuo problema è che per ognuna di queste operazioni impieghi O(N) per svolgerle, perchè la tua ricerca nel vettore è lineare, c’è una struttura dati della STL che ti può permettere di farlo in O(logN), le mappe

3 Mi Piace

Grazie mille, alla fine bastava aggiungere un altro break in quel punto (e togliere l’ else nella funzione togli), comunque si l’ultimo subtask è andato oltre il tempo però intanto ho preso mano con questo tipo di strutture :smile:

1 Mi Piace