Moisil++ 2023 Clasele 11-12 Mirror | Cătălin și sortarea binară

Într-o dimineață fatidică de iarnă, Cătălin a inventat un algoritm de sortare cu complexitatea $O(N)$, pe care l-a denumit "Sortare binară". Deși acest algoritm sfidează toate legile naturii, tot nu poate rezolva această problemă.

Cerință

Se dă un șir $a_1,a_2,\ldots,a_n$. Un șir $b_1,b_2,\ldots,b_n$ este o rearanjare a lui $a$ dacă $b$ conține aceleași elemente ca $a$, eventual în altă ordine.

De exemplu, rearanjări ale lui $a=[2,1,2,3]$ sunt $[2,1,2,3]$, $[3,2,1,2]$ sau $[1,2,2,3]$, dar nu și $[1,2,3,4]$ sau $[3,1,2,3]$.

Valoarea unei rearanjări $b_1,b_2,\ldots,b_n$ este egală cu $|b_1-b_2|+|b_2-b_3|+\ldots+|b_{n-1}-b_n|+|b_n-b_1|$, unde $|x|$ reprezintă modulul sau valoarea absolută a lui $x$.

De exemplu, valoarea lui $b=[3,1,2,2]$ este egală cu $|3-1|+|1-2|+|2-2|+|2-3|=2+1+0+1=4$.

În funcție de numărul cerinței $c$, va trebui să aflați:

• Dacă $c=1$, care este valoarea minimă posibilă a unei rearanjări $b_1,b_2,\ldots,b_n$ a șirului $a$?
• Dacă $c=2$, care este valoarea maximă posibilă a unei rearanjări $b_1,b_2,\ldots,b_n$ a șirului $a$?

Date de intrare

Pe prima linie a fișierului de intrare binsort.in se vor afla două numere $c$ și $n$ - numărul cerinței, respectiv lungimea șirului $a$.

Pe a doua linie se vor afla $n$ numere naturale $a_1,a_2,\ldots,a_n$ - elementele șirului $a$.

Date de ieșire

• Dacă $c=1$, atunci fișierul de ieșire binsort.out va conține valoarea minimă posibilă a unei rearanjări a șirului $a$, precum și orice rearanjare $b_1,b_2,\ldots,b_n$ cu valoarea minimă.
• Dacă $c=2$, atunci fișierul de ieșire binsort.out va conține valoarea maximă posibilă a unei rearanjări a șirului $a$, precum și orice rearanjare $b_1,b_2,\ldots,b_n$ cu valoarea maximă.

Restricții și precizări

• $1 \le n \le 2 \cdot 10^5$;
• $-10^9 \le a_i \le 10^9$;
• Pentru $20$ de puncte, $c=1$ și $n \le 2 \ 000$;
• Pentru încă $20$ de puncte, $c=1$;
• Pentru $30$ de puncte, $c=2$ și $n \le 2 \ 000$;
• Pentru încă $30$ de puncte, $c=2$.

Exemplul 1

binsort.in

1 5
2 3 1 2 1

binsort.out

4
3 2 2 1 1

Explicație

Valoarea rearanjării $[3,2,2,1,1]$ este egală cu $|3-2|+|2-2|+|2-1|+|1-1|+|1-3|=4$, care este minimul posibil.

Exemplul 2

binsort.in

2 5
2 3 1 2 1

binsort.out

6
1 3 1 2 2

Explicație

Valoarea rearanjării $[1,3,1,2,2]$ este egală cu $|1-3|+|3-1|+|1-2|+|2-2|+|2-1|=6$, care este maximul posibil.