•andunhill
|
|
« Răspunde #25 : Martie 10, 2010, 21:07:37 » |
|
Nu va mai chinuiti sa imi evaluati sursa. Am luat 100 pt . Am descoperit greseala.
|
|
|
Memorat
|
|
|
|
•impulse
Strain
Karma: 0
Deconectat
Mesaje: 2
|
|
« Răspunde #26 : Martie 11, 2010, 09:57:02 » |
|
De ce iau doar 90puncte? 1 test = TLE #include<stdio.h> #include<map> using namespace std; int main() { FILE *fin=fopen("livada.in","r"); FILE *fout=fopen("livada.out","w"); int m,n,p; fscanf(fin,"%d %d %d",&m,&n,&p); int mcon = 0, con = 0, last = -1, msoi = 0; int need = n / 2 + 1; for(int c = 0; c < m; c++) { last = -1; con = 0; map<int, int> v; int more = 1; for(int a = 0; a < n; a++) { int soi; fscanf(fin, "%d", &soi); if(more) { if(v.count(soi) == 0) { v.insert(pair<int,int>(soi,1)); } else { v[soi] = v[soi] + 1; if(v[soi] >= need) { more = 0; msoi++; } } } if(last != -1 && last == soi) { con++; if(con > mcon) mcon = con; } else con = 1; last = soi; } } fprintf(fout,"%d\n%d",msoi,mcon); fclose(fin); fclose(fout); return 0; }
|
|
|
Memorat
|
|
|
|
•SpiderMan
|
|
« Răspunde #27 : Martie 11, 2010, 10:07:21 » |
|
Ori nu e eficient algoritmul, ori ai o bucla infinita, incearca testele OJI.
|
|
« Ultima modificare: Martie 11, 2010, 16:32:45 de către Simoiu Robert »
|
Memorat
|
|
|
|
•Mishu91
|
|
« Răspunde #28 : Martie 11, 2010, 13:08:40 » |
|
Nu am citit foarte atent sursa, dar am văzut că folosești la un moment dat un map. Ai grijă că această structură este un mare consumator de timp și memorie, iar dacă o poți înlocui cu altceva, nu ezita.
|
|
|
Memorat
|
|
|
|
•tvlad
|
|
« Răspunde #29 : Martie 11, 2010, 19:03:04 » |
|
Am inlocuit cu si acum nu am primit decat cateva TLE si un Wrong answer. Vezi ca in functia maj ai un for in altul, complexitate O(n^2). Incearca sa reduci chestia asta si vei lua 100. (1<<x) este egal cu 2 x, si fiindca 2 31 iese din int, mai scadem 1. Sper sa te ajute!:D L.E: Am scos si cate un zero de la vectorii tai, ca nu intra in memorie. Ai grija ca, dupa cum ai zis si tu 2 31 iese din int, dar expresia e evaluata tot pe int. Castarea la unsigned ar rezolva problema. ((unsigned int)1 << 31)-1
|
|
|
Memorat
|
|
|
|
•freak93
|
|
« Răspunde #30 : Martie 12, 2010, 09:06:29 » |
|
@Vlad Chiar daca (1<<31) iese din int el asa va arata in baza 2 100....00(31 zerouri) care este perceput ca -231. Imediat ce scazi 1, iar depeseste limita int(de data asta cea inferioara) si ia valoare pe care o vreau.A stfel ca la (1<<31) adunam -1 (1<<31):10000000000000000000000000000000 (-1): 11111111111111111111111111111111 rezultat: 01111111111111111111111111111111
Observam ca primul bit(cel de semn) a fost adunat ca si ceilalti biti si s-a redus. Vreau sa marchez faptul ca indiferent cat de mari sunt numerele cu care faci operatii pe int, ele se vor executa ca si celelalte doar ca nu se vor tine cont de ceilalti biti. Aceste apelari nu sunt gresite(eu sincer le folosesc mereu cand nu trebuie sa adun maximul undeva). Ex: MAXT=(1<<31)-1; MINT=MAXT+1;(ne intoarcem inapoi in -231) La MINT am atribuit valoarea asa fiindca nu imi da mereu cum trebuie daca pun MINT=(1<<31);
|
|
|
Memorat
|
|
|
|
•impulse
Strain
Karma: 0
Deconectat
Mesaje: 2
|
|
« Răspunde #31 : Martie 12, 2010, 10:10:40 » |
|
Ori nu e eficient algoritmul, ori ai o bucla infinita, incearca testele OJI.
Apoi, cu algoritmu meu iau 100 de pct pe testele de la OJI... Nu am citit foarte atent sursa, dar am văzut că folosești la un moment dat un map. Ai grijă că această structură este un mare consumator de timp și memorie, iar dacă o poți înlocui cu altceva, nu ezita.
Ai vreo idee cu ce as putea inlocui map-u?
|
|
|
Memorat
|
|
|
|
•freak93
|
|
« Răspunde #32 : Martie 12, 2010, 10:56:27 » |
|
Mai complicat: ai putea inlocui map-ul cu un hash(daca nu stii ce inseamna iti sugerez sa rezolvi problema hashuri de la arhiva educationala) sau mult mai simplu sa te folosesti de faptul ca diferenta dintre cel mai mare si cel mai mic de pe un rand este de 250.000. Daca stii count sort il poti modifica un pic(scazand din toate numerele minimul) si astfel ai complexitate O(n*m). Map-ul are complexitate logaritmica asa ca e de preferat sa nu o folosesti in situatii in care poti folosi altceva mai rapid.
|
|
|
Memorat
|
|
|
|
•miculprogramator
|
|
« Răspunde #33 : Martie 14, 2010, 16:10:32 » |
|
Primesc o eroare pe care n-am mai intalnit-o pana acum Killed by signal 6(SIGABRT) - http://infoarena.ro/job_detail/417582 . Ma asteptam sa ia in jur de 40 de puncte, sau mai putin (rezolv numai prima cerinta deocamdata). E vreo problema la mine sau are ceva evaluatorul ?
|
|
|
Memorat
|
|
|
|
•stocarul
|
|
« Răspunde #34 : Martie 14, 2010, 16:35:34 » |
|
Problema e la tine. Din câte știu, e cauzată de împărtiri la 0....dar nu sunt sigur. Poți căuta pe forum/goagăl.
|
|
|
Memorat
|
|
|
|
•miculprogramator
|
|
« Răspunde #35 : Martie 14, 2010, 16:43:21 » |
|
Nu era de la impartirea cu 0. Faceam de doua ori fclose(g); , imi cer scuze ca am postat aiurea.
|
|
|
Memorat
|
|
|
|
•SpiderMan
|
|
« Răspunde #36 : Iunie 22, 2010, 17:20:59 » |
|
Se poate totusi lua in Pascal 100 pct .... fara citire parsata ( nu am incercat inca ) ?
[LE] Iau 80 cu citire parsata, cu un TLE si MLE, fara iau 3 TLE, adica 70 pct. [LE2] Am luat 100, am facut citirea parsata pe bucati ...
|
|
« Ultima modificare: Iunie 23, 2010, 20:10:16 de către Simoiu Robert »
|
Memorat
|
|
|
|
•rares192
Strain
Karma: 1
Deconectat
Mesaje: 12
|
|
« Răspunde #37 : Februarie 06, 2011, 16:46:12 » |
|
Ce poate sa aiba tesul 9 ca iau TLE si pe restu imi intra frumos de tot in timp..maxim 280 ms si limita e la 0.6 s ? http://infoarena.ro/job_detail/529958testele sunt aceleasi ca si cele de la OJI ?
|
|
|
Memorat
|
|
|
|
•VisuianMihai
|
|
« Răspunde #38 : Ianuarie 17, 2012, 16:11:56 » |
|
Incearca sa mai optimizezi putin algoritmul. Complexitatea e O(n).
|
|
|
Memorat
|
|
|
|
•S7012MY
|
|
« Răspunde #39 : Ianuarie 17, 2012, 16:53:57 » |
|
Ce poate sa aiba tesul 9 ca iau TLE si pe restu imi intra frumos de tot in timp..maxim 280 ms si limita e la 0.6 s ? http://infoarena.ro/job_detail/529958testele sunt aceleasi ca si cele de la OJI ? Limitele sunt super lejere, nu inteleg cum poti lua tle. O solutie cu sort din stl ia 100. Iti recomand sa citesti articolul asta http://infoarena.ro/problema-majoritatii-votului , e foarte bine scris si interesant.
|
|
|
Memorat
|
|
|
|
•klamathix
|
|
« Răspunde #40 : Ianuarie 17, 2012, 19:49:02 » |
|
Si voi doi aveti un pic de TLE. Omul n-a mai intrat pe forum de pe 27 mai.
|
|
|
Memorat
|
|
|
|
•TheNechiz
|
|
« Răspunde #41 : Iunie 27, 2012, 09:43:19 » |
|
Mai sunt limitele de timp așa lejere?
|
|
|
Memorat
|
|
|
|
•Steve
Client obisnuit
Karma: 36
Deconectat
Mesaje: 72
|
|
« Răspunde #42 : Iunie 27, 2012, 12:48:16 » |
|
Limita e ok, depinde cu ce citesti probabil...(si fara cin/cout ca is de 2 ori mai lente ) LE: si eu folosesc tot fstreamuri pt citire, dar din cate am auzit cin/cout sunt slabute...(cred ca wef a comentat asta la o problema mai demult)
|
|
« Ultima modificare: Iunie 28, 2012, 08:19:04 de către Stefan Eniceicu »
|
Memorat
|
|
|
|
•TheNechiz
|
|
« Răspunde #43 : Iunie 27, 2012, 18:56:09 » |
|
De acum am să folosesc numai scanf/printf.
|
|
« Ultima modificare: Iunie 27, 2012, 19:38:15 de către Birisan Razvan »
|
Memorat
|
|
|
|
•freak93
|
|
« Răspunde #44 : Iunie 27, 2012, 23:15:30 » |
|
Nu sunt de 2 ori mai lente. Eu sincer folosesc ifstream/ofstream si imi merge foarte bine(foarte rar chiar mai repede). Majoritatea problemelor sunt facute astfel incat sa intre citirea oricum ar fi ea. La asta de exemplu am citit/afisat cu streamuri.
L.E: Vad ca tu folosesti freopen cu cin/cout. De la o anumita versiune de gcc/g++ s-a implementat o chestie numita sync_with_stdin care strica aceasta pereche. Folosesti fie streamuri, fie freopen + scanf/print, fie cauti pe net cum sa dezactivezi sync_with_stdin
|
|
« Ultima modificare: Iunie 27, 2012, 23:32:56 de către Budau Adrian »
|
Memorat
|
|
|
|
•TheNechiz
|
|
« Răspunde #45 : Iunie 28, 2012, 09:48:55 » |
|
Mulțumesc pentru sfat.
|
|
|
Memorat
|
|
|
|
|