|
Titlul: 010 Distincte2 Scris de: Mihai-Alexandru Dusmanu din Aprilie 24, 2012, 20:53:06 Aici puteţi discuta despre problema Distincte2 (http://infoarena.ro/problema/distincte2).
Titlul: Răspuns: 010 Distincte2 Scris de: Andreea Dutulescu din Septembrie 09, 2012, 07:02:09 Memoria disponibila la problema distincte2 (http://"http://infoarena.ro/problema/distincte2") este foarte mica si programul elaborat de mine o depaseste. ](*,) :fighting:
Eu la sursa mea am economisit cata memorie am putut dar tot nu merge :readthis: Sursa mea este: :thumbdown: Cod: using namespace std; Ma puteti ajuta sa o fac mai eficienta????Sa mai economisesc memorie! :-k Multumesc! :D Editat de admin: De acum incolo, posteaza in topicul problemei (http://infoarena.ro/forum/index.php?topic=7803.0 (http://infoarena.ro/forum/index.php?topic=7803.0)) Titlul: Răspuns: 010 Distincte2 Scris de: Mircea Dima din Septembrie 09, 2012, 09:09:19 Memoria disponibila la problema distincte2 (http://"http://infoarena.ro/problema/distincte2") este foarte mica si programul elaborat de mine o depaseste. ](*,) :fighting: Eu la sursa mea am economisit cata memorie am putut dar tot nu merge :readthis: Sursa mea este: :thumbdown: using namespace std; #include<stdio.h> int i,n,mm,m,v[100001],a,q,l,x,y; int main() { freopen("distincte2.in","r",stdin); freopen("distincte2.out","w",stdout); scanf("%d%d",&n,&mm); for(i=1;i<=n;i++) { scanf("%d",&a); v[a]=1; if(m<a)m=a; } for(l=1;l<=mm;l++) { q=0; scanf("%d%d",&x,&y); for(i=1;i<=m;i++) { if(v[ i ]>0) { if(i>=x&&i<=y)q++; } } printf("%d\n",q); } return 0; } Ma puteti ajuta sa o fac mai eficienta????Sa mai economisesc memorie! :-k Multumesc! :D Tu folosesti ~400 KB memorie iar limita e de 16MB, deci iti intra sigur in memorie. Din cate vad, tu la citire faci v[a] = 1; unde 1 <= a <= 1.000.000 iar tu ai declarat vectorul de 100.000 In plus, daca vectorul v va tine doar valori 1 si 0, nu are sens sa-l declari int, pune-l char. La alt 2lea for nu trebuia sa mergi de la x la y ? In plus, nu te astepta la punctaj maxim, asta e o solutie triviala. Titlul: Răspuns: 010 Distincte2 Scris de: Nicu B. din Septembrie 09, 2012, 19:57:58 Memoria disponibila la problema distincte2 (http://"http://infoarena.ro/problema/distincte2") este foarte mica si programul elaborat de mine o depaseste. ](*,) :fighting: Eu la sursa mea am economisit cata memorie am putut dar tot nu merge :readthis: Sursa mea este: :thumbdown: Cod: using namespace std; Ma puteti ajuta sa o fac mai eficienta????Sa mai economisesc memorie! :-k Multumesc! :D Editat de admin: De acum incolo, posteaza in topicul problemei (http://infoarena.ro/forum/index.php?topic=7803.0 (http://infoarena.ro/forum/index.php?topic=7803.0)) Nu e bine cum faci, complexitatea ta finala e N*M (daca toate numerele pe care le citesti la inceput sunt distincte), ceea ce e imposibil in 0.25 sec. Daca vrei, iti dau un indiciu, ar trebui sa scoti M*logN sau ceva de genul ca sa-ti intre. P.S.: ca sa vezi daca nu cumva ai un element care deja s-a bagat, iti sugerez sa folosesti ori set (bagi elementul in set, si daca deja exista, nu mai il baga inca odata), ori sa folosesti un map (de ce? pentru ca nu are rost sa declari un vector de 1 000 000 000, cand tu ai maxim 100 000 elemente, pe care map-ul ti le pune astfel in memorie incat sa nu ai probleme). Succes :) Titlul: Răspuns: 010 Distincte2 Scris de: Mircea Dima din Septembrie 09, 2012, 20:44:54 P.S.: ca sa vezi daca nu cumva ai un element care deja s-a bagat, iti sugerez sa folosesti ori set (bagi elementul in set, si daca deja exista, nu mai il baga inca odata), ori sa folosesti un map (de ce? pentru ca nu are rost sa declari un vector de 1 000 000 000, cand tu ai maxim 100 000 elemente, pe care map-ul ti le pune astfel in memorie incat sa nu ai probleme). Succes :) Unde vezi tu 1.000.000.000 in enuntul problemei? eu vad 1.000.000 Titlul: Răspuns: 010 Distincte2 Scris de: Visan Radu din Septembrie 09, 2012, 20:46:32 Poti sa faci in O(N) fara set sau map. :ok:
Titlul: Răspuns: 010 Distincte2 Scris de: Nicu B. din Septembrie 09, 2012, 20:56:45 P.S.: ca sa vezi daca nu cumva ai un element care deja s-a bagat, iti sugerez sa folosesti ori set (bagi elementul in set, si daca deja exista, nu mai il baga inca odata), ori sa folosesti un map (de ce? pentru ca nu are rost sa declari un vector de 1 000 000 000, cand tu ai maxim 100 000 elemente, pe care map-ul ti le pune astfel in memorie incat sa nu ai probleme). Succes :) Unde vezi tu 1.000.000.000 in enuntul problemei? eu vad 1.000.000 Oops, imi cer scuze pentru inducerea in eroare. Nu stiu ce am avut la momentul cand am citit problema de am citit asa. In cazul asta merge f. bine si cu un bool de 1 milion. Scuze inca odata :-". Titlul: Răspuns: 010 Distincte2 Scris de: Nicolae Titus din Iulie 27, 2014, 00:56:09 La cineva ii intra in timp cu fstream? mie doar cu stdio imi intra in timp.
|