Misterioso TLE in "Suffissi"

Aiuto
1

Ciao a Tutti ,
provando a risolvere il problema suffissi ho ottenuto un bel TLE in alcuni degli ultimi testcase :triumph: .
Questo è il mio codice:

std::unordered_set<int> visited;
int array[100000];
int suffix[100000];

int main(){
    std::ios::sync_with_stdio(false);
    #ifdef EVAL
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int N,M;
    std::cin>>N>>M;
    for(int i=0; i < N ;i++)
	    std::cin>>array[i];

    for(int i=N-1; i >= 0 ;i--){
    	visited.insert(array[i]);
        suffix[i] = visited.size();
    }

    for(int i=0;i<M;i++){
        int T;
    	std::cin>>T;
    	std::cout<<suffix[T-1]<<std::endl;
    }
    return 0;
}

Ho calcolato la complessità e dovrebbe essere O(N+M) :confused:. Qualcuno riesce a spiegarmi dove sto sbagliando?

2

Prova a cambiare std::endl con ‘\n’, se la complessità è quella che dici tu dovrebbe bastare :wink:

3

Niente sempre 80/100 :sob:.
Un gran bel mistero…

4

La mia soluzione è praticamente identica alla tua ma utilizzo un set piuttosto che un unordered_set, che in realtà conosco molto poco e quindi non so dirti troppo in merito.

1 Mi Piace
5

Avevo già provato con i set , ma sono passato agli unordered visto che dovrebbero metterci mediamente un tempo costante per inserire nuovi elementi :grimacing:

Per controprova ho provato a sottomettere utilizzando i set, ma ottengo sempre 50~80

6

Ho provato a sottoporre la tua soluzione utilizzando fstream al posto di reindirizzare stdin/out e mi ha dato 100/100, sembra strano anche a me perché anche tu avevi messo sync_with_stdio(false) però non so che altro dire :sweat_smile:

7

Grazie Mille!!!
Ora sono molto confuso :upside_down:
Lascio ancora la conversazione aperta nella speranza che qualcuno mi spieghi questo strano comportamento dei file haha

1 Mi Piace