# Misterioso TLE in "Suffissi"

**URL:** <https://forum.olinfo.it/t/misterioso-tle-in-suffissi/644>\
**Category:** Aiuto\
**Created:** [19 Luglio 2016, 3:40pm UTC](https://forum.olinfo.it/t/misterioso-tle-in-suffissi/644 "2016-07-19T15:40:17Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![AleC](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/a/53a042/32.png) [@AleC](https://forum.olinfo.it/u/AleC)\
**Post date:** [19 Luglio 2016, 3:40pm UTC](https://forum.olinfo.it/t/misterioso-tle-in-suffissi/644/1 "2016-07-19T15:40:17Z")

</div>

Ciao a Tutti ,  
provando a risolvere il problema [suffissi](https://cms.di.unipi.it/#/task/suffissi/statement) ho ottenuto un bel TLE in alcuni degli ultimi testcase 😤 .  
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) 😕. Qualcuno riesce a spiegarmi dove sto sbagliando?

---

<div class="post-metadata">

**Author:** ![filippos](https://forum.olinfo.it/user_avatar/forum.olinfo.it/filippos/32/103_2.png) [@filippos](https://forum.olinfo.it/u/filippos)\
**Post date:** [19 Luglio 2016, 6:14pm UTC](https://forum.olinfo.it/t/misterioso-tle-in-suffissi/644/2 "2016-07-19T18:14:41Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![AleC](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/a/53a042/32.png) [@AleC](https://forum.olinfo.it/u/AleC)\
**Post date:** [19 Luglio 2016, 6:58pm UTC](https://forum.olinfo.it/t/misterioso-tle-in-suffissi/644/3 "2016-07-19T18:58:25Z")

</div>

Niente sempre 80/100 😭.  
Un gran bel mistero…

---

<div class="post-metadata">

**Author:** ![filippos](https://forum.olinfo.it/user_avatar/forum.olinfo.it/filippos/32/103_2.png) [@filippos](https://forum.olinfo.it/u/filippos)\
**Post date:** [19 Luglio 2016, 7:07pm UTC](https://forum.olinfo.it/t/misterioso-tle-in-suffissi/644/4 "2016-07-19T19:07:30Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![AleC](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/a/53a042/32.png) [@AleC](https://forum.olinfo.it/u/AleC)\
**Post date:** [19 Luglio 2016, 7:25pm UTC](https://forum.olinfo.it/t/misterioso-tle-in-suffissi/644/5 "2016-07-19T19:25:09Z")

</div>

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

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

---

<div class="post-metadata">

**Author:** ![filippos](https://forum.olinfo.it/user_avatar/forum.olinfo.it/filippos/32/103_2.png) [@filippos](https://forum.olinfo.it/u/filippos)\
**Post date:** [19 Luglio 2016, 7:53pm UTC](https://forum.olinfo.it/t/misterioso-tle-in-suffissi/644/6 "2016-07-19T19:53:49Z")

</div>

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 😅

---

<div class="post-metadata">

**Author:** ![AleC](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/a/53a042/32.png) [@AleC](https://forum.olinfo.it/u/AleC)\
**Post date:** [19 Luglio 2016, 8:11pm UTC](https://forum.olinfo.it/t/misterioso-tle-in-suffissi/644/7 "2016-07-19T20:11:57Z")

</div>

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