h2. Date de iesire

In fisierul $algsort.out$ veti tipari restul impartirii sumei <tex>S=\sum_{i=1}^N {i \cdot v[i]}</tex> la numarul $23456789$, unde $v[]$ este vectorul celor $N$ numere sortate in ordine crescatoare (si indexate incepand cu pozitia $1$). Pentru detalii despre calculul acestei sume, consultati sectiunea $Observatii$.

In fisierul $algsort.out$ veti tipari cele $N$ numere din fisierul de intrare, sortate in ordine crescatoare.

h2. Restrictii

table(example).
|_. algsort.in |_. algsort.out |
| 5

4 7 5 1 3 | 74 |
 
h3. Explicatie
 
Dupa sortare, vectorul v devine:
 
|_. i | 1 | 2 | 3 | 4 | 5 |
|_. v[i] | 1 | 3 | 4 | 5 | 7 |
 
Astfel, <tex>S=1 \cdot 1 + 2 \cdot 3 + 3 \cdot 4 + 4 \cdot 5 + 5 \cdot 7=74</tex>, iar restul impartirii acestui numar la $23456789$ este tot $74$.

4 1 7 5 1 3 | 1 1 3 4 5 7 |

h2. Observatii

Problema sortarii eficiente a datelor impune, in conditiile de fata, cateva particularitati de evaluare pe care le vom descrie in continuare:
 
h3. Citirea datelor
 

Limita de timp impusa este de $500 ms$, din care, pentru testele maxime, intre $150$ si $300 ms$ vor fi ocupate de citirea datelor. *Nu* este necesara folosirea functiilor specializate de citire a blocurilor de caractere (parsarea citirii) pentru a obtine punctajul maxim, insa recomandam folosirea stream-urilor C++, care se comporta mai bine in mediul de evaluare decat functiile de citire din libraria standard C.

h3. Scrierea rezultatelor
 
Fisierul de iesire nu va contine toate numerele afisate in ordine crescatoare deoarece dimensiunea lui ar creste foarte mult si, odata cu aceasta, si timpul de executie al programului. Astfel, cea mai mare parte a timpului alocat pentru executie ar fi ocupat de scrierea informatiilor in fisier, si nu de algoritm in sine. Din acest motiv, dupa ce vectorul de numere (il vom nota cu $v$) va fi sortat, va trebui calculata si tiparita suma $S$ conform cerintei. Valoarea acestei sume poate fi foarte mare, iesind din tipurile standard de date, iar pentru calculul ei ne vom folosi de faptul ca nu avem nevoie decat de restul impartirii ei la numarul $23456789$.
 
Acest numar este prim si mai mare decat valoarea maxima a lui $N$, in asa fel incat <tex>i \mod 23456789 \neq 0</tex>, pentru orice <tex>1 \leq i \leq N</tex>. De asemenea, niciun numar nenul din datele de test nu este divizibil cu $23456789$, asigurandu-ne astfel ca fost ales ca <tex>i \cdot v[i] \mod 23456789 \neq 0</tex>, pentru toate valorile <tex>\theta < i \leq N</tex>, unde <tex>\theta</tex> este numarul de elemente egale cu $0$ (care, dupa sortare, vor fi plasate la inceputul vectorului $v$). Daca, dimpotriva, ar fi existat astfel de produse divizibile la $23456789$, atunci elementele de pe pozitiile care le corespund ar fi putut fi schimbate oricum intre ele, fara sa modifice valoarea finala a rezultatului; in consecinta, un vector incorect sortat ar fi produs mai usor o valoare $S$ ce ar fi fost evaluata drept raspuns corect.
 
Calcularea valorii $S mod 23456789$ poate fi facuta pas cu pas (dupa soratea vectorului), folosind urmatoarea metoda, pe care o vom prezenta in pseudocod:
 
==code(c) |
S <- 0
pentru i <- 1, N
	S <- (S + i*v[i]) mod 23456789
sfarsit pentru
==
 
Singurul detaliu la care trebuie sa mai avem grija este faptul ca rezultatul inmultirii $i*v[i]$ poate depasi tipul de date in care se incadreaza factorii ei (intregi cu semn pe 32 de biti). De aceea, fie va trebui sa facem o conversie explicita catre un tip intreg pe 64 de biti ( $long long$ sau $int64$), fie ne vom folosi de particularitatile de limbaj sau de compilator, declarand unul dintre factorii produsului ca intreg pe 64 de biti.
 

h3. Structura testelor
Datorita largii varietati de algoritmi de sortare si comportarii lor diferite in functie de anumite particularitati structurale ale datelor de intrare, pentru evaluarea problemei se folosesc $5$ grupe de cate $4$ teste. Toate testele aflate in aceeasi grupa vor avea aceeasi valoare pentru $N$ si acelasi domeniu de valori pentru cele N numere: <tex>0 \le v[i] \le \lfloor N \cdot \gamma \rfloor</tex>, unde <tex>\gamma = \frac{2^{31}-1}{500000}</tex>. Valorile lui $N$ pentru cele 5 grupe de teste sunt $10$, $1.000$, $100.000$, $350.000$ respectiv $500.000$. Testele din cadrul fiecarei grupe se vor diferentia astfel:

* al treilea test va contine numerele sortate in ordine descrescatoare
* al patrulea test va contine numerele in ordine aleatoare, insa vor exista putine perechi de numere distincte (foarte multe dintre numere vor aparea de mai multe ori in fisierul de intrare)

h3. Limite de timp si memorie
 
Limitele de timp si memorie au fost alese in asa fel incat punctajul maxim sa poata fi obtinut doar de implementari bune ale unor algoritmi de sortare eficienti atat din punct de vedere al timpului de executie (complexitatea ceruta este <tex>\mathit{O}\left( N \cdot \log N \right)</tex>), cat si din punct de vedere al memoriei suplimentare folosite (<tex>\mathit{O}\left( \log N \right)</tex> memorie suplimentara admisa).
 

h2. Solutie
Structura problemei cere implementarea unui 'algoritm de sortare pe baza de comparatii':http://en.wikipedia.org/wiki/Comparison_sort. Exista, de asemenea, algoritmi de sortare care nu compara explicit elementele si care au performante mai bune pentru anumite cazuri particulare ale structurii datelor de intrare; acestia nu se preteaza insa cerintelor impuse in cazul de fata.