•dushmi
|
|
« : Aprilie 24, 2012, 20:53:06 » |
|
Aici puteţi discuta despre problema Distincte2.
|
|
|
Memorat
|
|
|
|
•andreeainfo_d
Strain
Karma: -29
Deconectat
Mesaje: 11
|
|
« Răspunde #1 : Septembrie 09, 2012, 07:02:09 » |
|
Memoria disponibila la problema distincte2 este foarte mica si programul elaborat de mine o depaseste. Eu la sursa mea am economisit cata memorie am putut dar tot nu merge Sursa mea este: 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! Multumesc! Editat de admin: De acum incolo, posteaza in topicul problemei (http://infoarena.ro/forum/index.php?topic=7803.0)
|
|
« Ultima modificare: Septembrie 09, 2012, 13:48:36 de către Mihai-Alexandru Dusmanu »
|
Memorat
|
|
|
|
•blasterz
|
|
« Răspunde #2 : Septembrie 09, 2012, 09:09:19 » |
|
Memoria disponibila la problema distincte2 este foarte mica si programul elaborat de mine o depaseste. Eu la sursa mea am economisit cata memorie am putut dar tot nu merge Sursa mea este: 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! Multumesc! 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.
|
|
|
Memorat
|
|
|
|
•NicuCJ
Strain
Karma: 6
Deconectat
Mesaje: 44
|
|
« Răspunde #3 : Septembrie 09, 2012, 19:57:58 » |
|
Memoria disponibila la problema distincte2 este foarte mica si programul elaborat de mine o depaseste. Eu la sursa mea am economisit cata memorie am putut dar tot nu merge Sursa mea este: 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! Multumesc! Editat de admin: De acum incolo, posteaza in topicul problemei (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
|
|
|
Memorat
|
|
|
|
•blasterz
|
|
« Răspunde #4 : 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
|
|
|
Memorat
|
|
|
|
•visanr
|
|
« Răspunde #5 : Septembrie 09, 2012, 20:46:32 » |
|
Poti sa faci in O(N) fara set sau map.
|
|
|
Memorat
|
|
|
|
•NicuCJ
Strain
Karma: 6
Deconectat
Mesaje: 44
|
|
« Răspunde #6 : 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 :-".
|
|
|
Memorat
|
|
|
|
•nicolaetitus12
Strain
Karma: 0
Deconectat
Mesaje: 10
|
|
« Răspunde #7 : Iulie 27, 2014, 00:56:09 » |
|
La cineva ii intra in timp cu fstream? mie doar cu stdio imi intra in timp.
|
|
|
Memorat
|
|
|
|
|