Eu am N^2 * (hash) la Plagiat.
Sunt curios, i-a intrat cuiva N^3? Eu asa am avut in prima idee si a luat 90 sursa.

PS: De la ce e log-ul vostru din complexitate, sortare?

Am incercat-o si eu ieri, si iau TLE 12 sau ceva de genul.. ce complexitate ati scos?
Eu am gasit in O(x log n + x), unde x este numarul de elemente din matrice (x = n * n), iar log-ul e de la calcularea ordinii elementelor pe linie / coloana (nu dau spoilere, cu toate ca e destul de simplu). Se poate totusi calcula in O(x) ordinea?

[am citit cu atentie enuntul si modul de interactiune]

Offtopic:

iar pe interactiva am citit cu atentie enuntul si modul de interactiune si asa am observat ca trebuia sa citesc acel 1 de confirmare a raspunsului corect.

Mersi mult, in sfarsit mi-am dat seama si eu de ce am luat 0 )

Iar s-a blocat evaluatorul
De ce se blocheaza in fiecare zi (cel putin azi si ieri) la aprox. ora 10?

    Salut. Poate cineva sa-mi spuna cum pot masura timpul de executiei al programului meu in Free Pascal ?
    De ex. daca problema mea are 2 cerinte , si mi-a facut-o pe prima , vreau sa stiu daca mai am timp sa o fac si pe a doua pe testul respectiv, sau trebuie sa dau primul rezultat si sa se opreasca programul.

Iti poti calcula complexitatea care ar trebui sa-ti iasa din algoritmul/algoritmii respectivi (gen O(n^2), O(nlogn) etc).
Daca iti intra pentru ambele cerinte, atunci ar trebui sa le scrii pe amandoua.. (deobicei daca nu iti intra cerinta a2-a in timp e pentru ca ai un algoritm ineficient, nu pentru ca cerinta 1 + cerinta 2 (rezolvate eficient amandoua) ar avea constanta prea mare sau ceva.. la ONI din cate stiu nu prea se dau probleme de optimizari idioate)
Oricum, cred ca mai bine nu ai incerca sa masori timpul de executie in felul acesta, pentru ca s-ar putea sa-ti iei de multe ori teapa. Ma refer ca nu prea poti stii diferenta dintre calculatorul pe care esti tu la concurs si cel pe care se face evaluarea (ala de la concurs in general are procesorul mai slab, si 2 secunde pe ala pot fi 0.5 pe cel cu evaluarea... astfel tu poti sa crezi ca nu intra si sa nu mai faci deloc cerinta 2). Uite, de exemplu, eu am i7 si tot imi merge de vreo 2-3 ori mai lent decat pe evalul de pe infoarena (si eu tot pe linux sunt).
Sper ca te-am lamurit cat de cat
Bafta in continuare.

Am si eu un frate in clasa a6-a, si nu am gasit site la el
Oricum, chestia e ca olimpiada la gimnaziu este peste vreo 3 saptamani, deci mai e timp (si site-ul de la oni liceu doar a aparut azi sau ieri)

Iar a picat evaluatorul
Ce se intampla de pica asa de des (aproape in fiecare zi) in ultimele 2 sapt?

Nu stiu daca te-au mintit neaparat )
Ideea e ca pe unele compilatoare (sau platforme) headerele nu ocupa memorie in plus. Dar aici (si la alte concursuri din Romania) am observat chestia asta... si na, cautam si eu o explicatie

Pai eu am trimis 2 surse, prima are headerele puse si are 400 kb, a2-a e identica (inafara de headerele pe care le-am sters) si are 240

Vroiam ca lumea sa citeasca de mai multe ori din fisier. Cred ca tebuia sa pun limita de memorie mai mica da asta e.

Eu am 400 kb, si am declarat doar 2 fisiere si vreo 5 variabile...
Totusi, am asa multa memorie din cauza ca pun headere la gramada, de care nici macar nu am nevoie.
Am scos acum 240 kb...
Totusi, imi explica cineva va rog de ce evaluatorul de pe infoarena (si am vazut ca si la concursuri) ia atata memorie de la headere?
Adica, pe codeforces de exemplu nu stiu sa fie asa (am vazut oameni care-si puneau toate headerele posibile si aveau memorie folosita foarte mica, gen sursa asta http://ideone.com/LwfbPu , la problema 280A - are memorie 0 kb (cam cat ar trebui pentru o functie si 3 variabile - http://www.codeforces.com/submissions/rng_58 ))

Nice one!

Priviti noua generatie ! Aplauda-te fiule !

Nu vreau sa fiu rau (sau poate ca vreau cu tine), dar nu inteleg de ce-ti dai tu aiurea cu parerea.
In primu rand, nici nu ai "curajul" sa-ti pui numele adevarat, deci tot ce spui e degeaba (pot si eu sa-mi fac un mail fantoma si sa-l injur tot poporul de la un internet cafe, ca nu cred ca ma prinde nimeni)
In al doilea rand, te-ai calificat oare vreodata la vreo nationala sa ai "dreptul" sa judeci sfaturile astea?
Iti spun eu ca din aia 2000 si cati ai spus tu care au luat 0, mai mult de 90% nici nu au auzit de infoarena. Au mers la OJI doar ca sa scape de ore (cum mai stiu si eu unele cazuri.... crede-ma ca sunt din ce in ce mai multe)
Asa ca, nu vad care ar fi problema?? Aici sunt niste sfaturi, NU TE OBLIGA ABSOLUT NIMENI sa le respecti sau nu.
Plus ca, in aia 2000 si ceva intra si cei de gimnaziu, care crede-ma ca habar nu au ce-i cu ei (de exemplu, eu in clasa a5-a, am participat doar ca nu aveam ce face)
Asa ca, inainte sa mai pui ceva pe forum la vederea tuturor, gandeste-te inainte (si eventual pune-ti semnatura.. daca te tine)

Problema a2-a a fost un jeg (prima era usoara intr-adevar, dar tot era ambigua cu "pozitii ocupate" si "pozitii luate" - sau ceva de genul asta)...
La a2-a trebuiau afisate in ordinea 1, 2, 3 ... N
Adica daca aveai clepsidrul sau cum se chema in starea 2, trebuia sa le afisezi tot in ordinea 1, 2, 3 ...

Mi s-a intamplat doar mie sa iau WA cand afisez LL-uri cu cstdio si OK cu stream? Ma refer in general, nu am patit-o la olimpiada. Care ar fi motivul pt care se intampla asta?

Nu, la prima am folosit stdio. La a doua am folosit streamuri pentru ca aveam de afisat un long long, si nu eram sigur daca il afisez cu %lld sau %I64d, asa ca am afisat cu streamuri. Am aflat de asemenea ca este nerecomandat sa citesti cu stdio si sa afisezi cu streamuri, asa ca am facut si citirea cu fstream. Nu mai fac aceeasi greseala niciodata.

Cod:

inline void printLongLong(long long foo)
{
    if (foo == 0) return ;
    printLongLong(foo / 10);
    printf("%d", foo % 10);
}

Eu zic ca ar merge asa daca ai putine nr de afisat...

sau sa transformi long long-ul ala al tau in 2 int-uri (adica foo / 1000000000 si foo % 1000000000) si sa faci ca la numere mari in baza 10^9
sau ar mai merge sa parsezi afisarea

Bineinteles, asta numai in cazul in care aveai de afisat un singur long long (sau foarte putine oricum...) ... bulanelile astea mananca timp la greu (nu stiu care a fost exact situatia la clasa a8-a)

PS: Eu am pierdut in a6-a locul 1 la ONI din cauza ca afisam long-uri cu %d pe borland... asa ca nu va mai ofticati degeaba, "inca n-ati pierdut nimic" )

PS2: Ce parere aveti de subiectele de la a 9-a? Eu prima data cand le-am vazut am crezut ca le-au incurcat cu cele pentru bacul la romana ...

E buna ideea intr-adevar ... bravo
Oricum, cred ca modulo-urile alea mananca o droaie de-a timp (cred ca de la asta ai atatea TLE-uri)

GG

Steve: Eu am facut cu eps 0.000001 si mi-a mers....
Dan Alex: Stai putin, tu la ce te referi cu set? Ala din "#include <set>" ? Daca da, ala e logn (mai mult de fapt).. si nu mai iese o(n) solutia

Am incercat 3 modalitati , insa fara succes. Am pastrat hashing-ul pentru numere reale( cel cu partea fractionala) , folsind constanta propusa de Knuth si modulo 10007.

Eu tot nu prea vad cum cu hash.. tot trebuiau sortate numerele pana la urma
Daca ai ceva de genul:

Cod:

3
1
2

(astea sunt distantele, "sa presupunem" ca se poate),
atunci ce faci?

@ SebiSebi : Ce functie de hashing ai folosit ?

LE : Ma refer la faptul ca aveai de retinut double-uri.

Puteai inmulti numerele double cu 10^7, astfel ti le tineai long long-uri

Ai dreptate Rares, dar daca am deja cateva elemente in stiva de exit, cum pot rasturna stiva de entry?

Pai cred ca merge oricum, adica tu atunci cand inserezi un element nou intr-o stiva verifici daca nu cumva ai inserat in total mai mult de 15000.

Da, intr-adevar faza cu 500 000 a fost cam derutanta ...
Pe un test de genul

Cod:

30000
push_back(999999)
push_back(999998)
push_back(999997)
...
push_back(970001)
pop_front()

Pe ultima linie o sa ai cam 700 000

Oricum, facand o paranteza de la subiect (cel cu coca cola), chestia faina e ca inca te poti dezinscrie

O idee care mi-a venit mai demult, dar tot am uitat s-o scriu:

Ar fi frumos daca s-ar implementa pentru fiecare problema un fel de interfata de testare, adica sa-ti pui sursa si un test facut de tine, si sa-ti afiseze daca da la fel cu sursa oficiala sau nu (sau eventual sa sa-ti dea chiar out-ul sursei oficiale, care sa fie pus intr-un fisier pe care sa-l poti descarca (care dupa un minut sa se "autodistruga" desigur) ).
Asa nu ar mai fi intrebari pe forum de genul: "Cat va da pentru urmatorul test?".
Oricum, ma gandesc ca e greu de implementat chestia asta si ca siteul s-ar putea bloca asa, de o sursa care face ciclu infinit de exemplu, sau daca s-ar face prea multe incarcari si ar fi prea multe fisiere dintr-astea (eventual se poate pune captcha) ... dar eu zic ca ar fi interesant

Felicitari din toata inima baieti, ati dat lovitura din nou  

Uite ca ne-ati facut iar mandrii ca suntem romani, felicitari si tineti-o tot asa si in a2-a zi
PS (mai mult de off-topic): A mai observat cineva ca in "Last name" e defapt al doilea prenume? (cel putin asa vad la echipa noastra, la ceilalti nu stiu daca o fi la fel)