Fişierul intrare/ieşire: | zigsort.in, zigsort.out | Sursă | ONIS 2014, Runda 3 |
Autor | Paul Diac, Stefan Ciobaca | Adăugată de | |
Timp execuţie pe test | 0.5 sec | Limită de memorie | 20480 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Zigsort
Fie un vector de numere naturale A[] ce contine N elemente cu valori distincte. O sortare in zig-zag de ordin k se defineste ca o rearanjare a elementelor astfel incat :
a1 > a2 > ... > ak > ak+1
ak+1 < ak+2 < ... < a2*k+1
a2*k+1 > a2*k+2 > ... > a3*k+1
si asa mai departe, adica :
primele k + 1 elemente trebuie sa fie in ordine descrescatoare
elementele de la pozitiile k + 1 pana la 2 * k + 1 trebuie sa fie in ordine crescatoare
elementele de la pozitiile 2 * k + 1 pana la 3 * k + 1 trebuie sa fie in ordine descrescatoare
In general elementele de la pozitiile p * k + 1 pana la (p + 1) * k + 1 trebuie sa fie in ordine descrescatoare daca p este par si crescatoare daca p este impar.
Pentru a rezolva problema trebuie sa implementati o astfel de sortare dar care sa foloseasca interschimbari doar de elemente care sunt pe pozitii consecutive (swap A[i] si A[i+1]).
Date de intrare
Fişierul de intrare zigsort.in contine pe prima linie un numar natural T reprezentand numarul de teste apoi urmeaza descrierile fiecarui test:
Pe prima linie numerele N si K separate printr-un spatiu.
Pe urmatoarea linie N numere naturale, valorile initiale ale vectorului A[].
Date de ieşire
În fişierul de ieşire zigsort.out afisati pentru fiecare test, pe cate o linie, interschimarile de tipul celor descrise care sorteaza vectorul A[] transformandu-l intr-un vector zigsortat de ordin K:
Primul numar M reprezinta numarul de interschimbari necesare iar urmatoarele M numere reprezinta indici i pentru care se apeleaza swap(A[i], A[i+1]), in aceasta ordine astfel incat la final sa avem rezultatul dorit.
Restricţii
- 1≤ N ≤ 100000
- 1 ≤ K ≤ 4 ≤ N
- 1 ≤ A[i] ≤ 100000 pentru orice i
- Daca K > 1 atunci N % K = 1 (toate secventele monotone au lungime K).
- Programul va fi punctat doar daca pentru orice test M ≤ 375000 iar interschimbarile sunt valide (pozitiile i sunt din intervalul [1, N-1], si aplicate in ordinea in care au fost afisate sorteaza vectorul conform restrictiilor).
- In fisierul de intrare vor fi maxim 20 teste.
Exemplu
zigsort.in | zigsort.out |
---|---|
2 4 1 5 6 3 1 7 3 6 7 5 3 2 1 9 | 2 1 2 4 1 4 5 4 |
Explicatie
Pentru primul test reprezentam interschimbarile:
1 2 3 4
5 6 3 1 -> A[] initial, la final trebuie ca A[1]
> A[2]
< A[3]
> A[4]
aplicam swap(1,2) =>
6 5 3 1
aplicam swap(2,3) =>
6 3 5 1
care respecta 6 > 3 < 5 > 1.
Au fost necesare 2 interschimbari, pozitia 1 cu 2 si apoi 2 cu 3.