Zigsort

zigsort

== include(page="template/taskheader" task_id="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 :

Fie un vector de numere naturale *A[]* ce contine *N* elemente. O sortare in zig-zag de ordin *k* se defineste ca o reanranjare a elementelor astfel incat :

a{~1~} > a{~2~} > ... > a{~k~} > a{~k+1~}

a{~1~} ≥ a{~2~} ≥ ... ≥ a{~k~} ≥ a{~k+1~}

a{~k+1~} < a{~k+2~} < ... < a{~2*k+1~}

a{~k+1~} ≤ a{~k+2~} ≤ ... ≤ a{~2*k+1~}

a{~2*k+1~} > a{~2*k+2~} > ... > a{~3*k+1~}

a{~2*k+1~} ≥ a{~2*k+2~} ≥ ... ≥ a{~3*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

primele _*k*_ elemente trebuie sa fie in ordine necrescatoare
elementele de la pozitiile _*k + 1*_ pana la _*2 * k + 1*_ trebuie sa fie in ordine nedescrescatoare
elementele de la pozitiile _*2 * k + 1*_ pana la _*3 * k + 1*_ trebuie sa fie in ordine necrescatoare

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.

In general elementele de la pozitiile _*p * k + 1*_ pana la _*(p + 1) * k + 1*_ trebuie sa fie in ordine necrescatoare daca _*p*_ este par si nedescrescatoare 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]*).

Pentru a rezolva problema trebuie sa implementati o astfel de sortare dar care sa foloseasca interschibari doar de elemente care sunt pe pozitii consecutive (swap *A[i]* si *A[i+1]*).

h2. Date de intrare

h2. Restricţii

* 1≤ N ≤ 100000

* 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).

* Daca K > 1 atunci N % K = 1 (toate secventele necrescatoare / nedescrescatoare 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.

* In fisierul de intrate vor fi maxim 10 teste.

h2. Exemplu

  4 1
  5 6 3 1
  7 3

  6 7 5 3 2 1 9

  6 7 5 3 2 1 9 10

| 2 1 2
  4 1 4 5 4
|

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]@

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) =>

9721