Cătălin și sortarea binară

Time limit: 1s Memory limit: 256MB Input: binsort.in Output: binsort.out

Într-o dimineață fatidică de iarnă, Cătălin a inventat un algoritm de sortare cu complexitatea O(N)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 a1,a2,,ana_1,a_2,\ldots,a_n. Un șir b1,b2,,bnb_1,b_2,\ldots,b_n este o rearanjare a lui aa dacă bb conține aceleași elemente ca aa, eventual în altă ordine.

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

Valoarea unei rearanjări b1,b2,,bnb_1,b_2,\ldots,b_n este egală cu b1b2+b2b3++bn1bn+bnb1|b_1-b_2|+|b_2-b_3|+\ldots+|b_{n-1}-b_n|+|b_n-b_1|, unde x|x| reprezintă modulul sau valoarea absolută a lui xx.

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

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

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

Date de intrare

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

Pe a doua linie se vor afla nn numere naturale a1,a2,,ana_1,a_2,\ldots,a_n - elementele șirului aa.

Date de ieșire

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

Restricții și precizări

  • 1n21051 \le n \le 2 \cdot 10^5;
  • 109ai109-10^9 \le a_i \le 10^9;
  • Pentru 2020 de puncte, c=1c=1 și n2 000n \le 2 \ 000;
  • Pentru încă 2020 de puncte, c=1c=1;
  • Pentru 3030 de puncte, c=2c=2 și n2 000n \le 2 \ 000;
  • Pentru încă 3030 de puncte, c=2c=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][3,2,2,1,1] este egală cu 32+22+21+11+13=4|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][1,3,1,2,2] este egală cu 13+31+12+22+21=6|1-3|+|3-1|+|1-2|+|2-2|+|2-1|=6, care este maximul posibil.

Log in or sign up to be able to send submissions!