Ho completato al 70% chat. Ora per velocizzarlo ho pensato di utilizzare un unordered_set in modo tale da “lasciar perdere” i doppioni. A questo punto va tutto bene, l’unico problema è che mi da in tutti i sub task almeno un caso di test errato (se non di più).
Questo è il codice:
#include <iostream>
#include <fstream>
#include <unordered_set>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
int N;
string contenitore[1000000];
unordered_set<string> prova;
vector<string> ultimo;
int main()
{
ifstream in("input.txt");
ofstream out("output.txt");
cin >> N;
for(int i = 0; i < N; i++)
cin >> contenitore[i];
// inserisco nel set i nomi partendo dal fondo
for(int i = N-1; i >= 0; i--)
prova.insert(contenitore[i]);
// inserisco in un vettore i nomi che sono contenuti nel unordered_set
for(unordered_set<string>::iterator i = prova.begin(); i != prova.end(); i++)
ultimo.push_back(*i);
for(int i = ultimo.size()-1; i >= 0; i--)
cout << ultimo[i] << endl;
}
P.S: Ho provato i test case, in locale, e me li esegue correttamente ma nel correttore uno dei due è errato.
Il problema sta nel fatto che nell’unordered_set l’inserimento di un nuovo elemento viene eseguito in una posizione casuale, non sempre all’inizio (ecco un esempio).
Piuttosto, per risolvere il problema è corretto usare un unordered_set (ma anche un set, non fa differenza), ma solo per tenere traccia degli utenti già “visti”. Guardati il metodo count, torna parecchio utile
1 Mi Piace
Se ti può essere utile io ho utilizzato 2 map opposte: una con le chiavi che erano gli elementi dell’altra e viceversa
Comunque dovrei aver risolto con questo codice:
#include <iostream>
#include <fstream>
#include <unordered_set>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
int N;
string contenitore[1000000];
unordered_set<string> prova;
vector<string> ultimo;
int grandezza_precedente = 0;
int main()
{
ifstream in("input.txt");
ofstream out("output.txt");
cin >> N;
for(int i = 0; i < N; i++)
cin >> contenitore[i];
for(int i = N-1; i >= 0; i--)
{
prova.insert(contenitore[i]);
if(prova.size() > grandezza_precedente)
{
cout << contenitore[i] << endl;
grandezza_precedente++;
}
}
}
Dico che dovrei aver risolto per il semplice fatto che in questo momento il compilatore non funziona.