Pagini: 1 [2]   În jos
  Imprimă  
Ajutor Subiect: Limite de timp  (Citit de 31694 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
darkseeker
De-al casei
***

Karma: 29
Deconectat Deconectat

Mesaje: 106



Vezi Profilul
« Răspunde #25 : Martie 13, 2014, 12:17:34 »

Salut,

Cred ca limita la problema xmoto e un pic cam stransa. Am o sursa care lua 100 inainte si acum ia 95 cu TLE pe ultimul test.
Memorat
Vman
Echipa infoarena
Vorbaret
*****

Karma: 45
Deconectat Deconectat

Mesaje: 176



Vezi Profilul
« Răspunde #26 : Martie 13, 2014, 13:19:00 »

Am verificat limita si pare ok. Iti recomand ca atunci cand sortezi vectori de structuri sa nu sortezi direct vectorul ci sa iti iei un vector de indici cu care sa sortezi, pentru ca nu e eficient sa tot copiezi elemente dintr-o structura cu multi membri.

Exemplu:
Cod:
for (int i=0; i<N; ++i)
    ind[i] = i;
sort(ind, ind+N, cmp);

iar in cmp si peste tot pe unde mai ai nevoie te folosesti de vectorul de indici sortati:
Cod:
int cmp(...) {
return structura[ a ].membru < structura[ b ].membru
}
...
printf("%d\n", structura[ ind[i] ].membru);
Memorat
Thomas
Strain


Karma: -15
Deconectat Deconectat

Mesaje: 7



Vezi Profilul
« Răspunde #27 : Martie 13, 2014, 21:39:37 »

La xmoto am aceeasi problema. Iau 90p cu TLE pe 2 teste, cu complexitate NlogN pe sortare si N in rest. E sort-ul din stl mai rapid decat qsort-ul?
Memorat
Dddarius95
Client obisnuit
**

Karma: 30
Deconectat Deconectat

Mesaje: 66



Vezi Profilul
« Răspunde #28 : Martie 14, 2014, 22:16:20 »

La xmoto am aceeasi problema. Iau 90p cu TLE pe 2 teste, cu complexitate NlogN pe sortare si N in rest. E sort-ul din stl mai rapid decat qsort-ul?
Da, este.
Memorat
Y0da1
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« Răspunde #29 : August 05, 2017, 11:29:09 »

Nu situ daca cineva se mai uita pe topicul asta (ultimul post e din 2014) dar la problema scmax sursa oficiala (#2008093) cu AIB precum si alte implementari cu aceeasi idee (#2008090) obtin TLE pe testul 9.
Memorat
Pagini: 1 [2]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines