Pagini: 1 [2]   În jos
  Imprimă  
Ajutor Subiect: 985 Livada  (Citit de 8609 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
andunhill
Vorbaret
****

Karma: 12
Deconectat Deconectat

Mesaje: 183



Vezi Profilul
« Răspunde #25 : Martie 10, 2010, 21:07:37 »

Nu va mai chinuiti sa imi evaluati sursa. Am luat 100 pt  Winner 1st place . Am descoperit greseala.
Memorat
impulse
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 2



Vezi Profilul
« Răspunde #26 : Martie 11, 2010, 09:57:02 »

De ce iau doar 90puncte? 1 test = TLE

Cod:
#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
Nu mai tace
*****

Karma: -463
Deconectat Deconectat

Mesaje: 937



Vezi Profilul
« 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
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« 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. Smile
Memorat
tvlad
De-al casei
***

Karma: 63
Deconectat Deconectat

Mesaje: 121



Vezi Profilul
« Răspunde #29 : Martie 11, 2010, 19:03:04 »

Am inlocuit
Cod:
min1=250000;
cu
Cod:
min1=(1<<31)-1;
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 2x, si fiindca 231 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 231 iese din int, dar expresia e evaluata tot pe int.
Castarea la unsigned ar rezolva problema.
Cod:
((unsigned int)1 << 31)-1
Memorat
freak93
Echipa infoarena
Nu mai tace
*****

Karma: 342
Deconectat Deconectat

Mesaje: 819



Vezi Profilul
« 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 Deconectat

Mesaje: 2



Vezi Profilul
« Răspunde #31 : Martie 12, 2010, 10:10:40 »

Citat
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...

Citat
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
Echipa infoarena
Nu mai tace
*****

Karma: 342
Deconectat Deconectat

Mesaje: 819



Vezi Profilul
« 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
Nu mai tace
*****

Karma: 65
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« 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 ?  Confused
Memorat
stocarul
Nu mai tace
*****

Karma: 49
Deconectat Deconectat

Mesaje: 203



Vezi Profilul
« 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
Nu mai tace
*****

Karma: 65
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« 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.  Embarassed
Memorat
SpiderMan
Nu mai tace
*****

Karma: -463
Deconectat Deconectat

Mesaje: 937



Vezi Profilul
« 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 Deconectat

Mesaje: 12



Vezi Profilul
« 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/529958

testele sunt aceleasi ca si cele de la OJI ?
Memorat
VisuianMihai
De-al casei
***

Karma: -9
Deconectat Deconectat

Mesaje: 121



Vezi Profilul
« Răspunde #38 : Ianuarie 17, 2012, 16:11:56 »

Incearca sa mai optimizezi putin algoritmul.
Complexitatea e O(n).
Memorat
S7012MY
Nu mai tace
*****

Karma: 26
Deconectat Deconectat

Mesaje: 648



Vezi Profilul
« 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/529958

testele 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
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« 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
De-al casei
***

Karma: 30
Deconectat Deconectat

Mesaje: 145



Vezi Profilul
« Răspunde #41 : Iunie 27, 2012, 09:43:19 »

Mai sunt limitele de timp așa lejere? Whistle
Memorat
Steve
Client obisnuit
**

Karma: 36
Deconectat Deconectat

Mesaje: 72



Vezi Profilul
« 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 Thumb down)

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
De-al casei
***

Karma: 30
Deconectat Deconectat

Mesaje: 145



Vezi Profilul
« Răspunde #43 : Iunie 27, 2012, 18:56:09 »

De acum am să folosesc numai scanf/printf. Shocked

« Ultima modificare: Iunie 27, 2012, 19:38:15 de către Birisan Razvan » Memorat
freak93
Echipa infoarena
Nu mai tace
*****

Karma: 342
Deconectat Deconectat

Mesaje: 819



Vezi Profilul
« 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
De-al casei
***

Karma: 30
Deconectat Deconectat

Mesaje: 145



Vezi Profilul
« Răspunde #45 : Iunie 28, 2012, 09:48:55 »

Mulțumesc pentru sfat. Ok
Memorat
Pagini: 1 [2]   În sus
  Imprimă  
 
Schimbă forumul:  

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