Fişierul intrare/ieşire:compact3.in, compact3.outSursăONI 2019, clasele 11-12, ziua 2
AutorAlex TatomirAdăugată deTincaMateiTinca Matei TincaMatei
Timp execuţie pe test1.4 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Compact3

Se dă un şir a de N numere naturale nenule mai mici sau egale cu M. Se doreşte partiţionarea şirului în cât mai multe grupe stabile. O grupă stabilă se defineşte ca fiind o secvenţă continuă şi nevidă de numere a_{s}, a_{(s + 1)}, a_{(s + 2)}, ..., a_{(d - 1)}, a_{d}, respectând următoarea condiţie:

  • orice alt element din afara intervalului [s, d] este ori strict mai mare, ori strict mai mic decât toate valorile din [s, d].

Mai exact, pentru orice i \notin [s, d], doar una din următoarele condiţii este satisfăcută:

  1. a[i] < a[j], oricare ar fi s <= j <= d;
  2. a[i] > a[j], oricare ar fi s <= j <= d.

Partiţionarea şirului presupune ca fiecare număr să facă parte din exact o grupă.

Cerinţă

Dându-se N, M şi şirul a de N numere, să se găsească o partiţie a şirului a în cât mai multe grupe stabile.

Date de intrare

În fişierul compact3.in, pe prima linie se află două numere N şi M separate prin spaţiu. Pe a doua linie se află cele N elemente ale şirului a separate prin câte un spaţiu.

Date de ieşire

În fişierul compact3.out se vor afişa două linii. Pe prima linie se va afla numărul maxim de grupe stabile G, iar pe a doua linie se vor afla G valori, reprezentând valori, reprezentând poziţia ultimului element al fiecărei grupe stabile în ordine crescătoare.

Restricţii

  • 1 \leq N \leq 1.000.000.
  • 1 \leq M \leq N.
  • 1 \leq a[i] \leq M, pentru 1 \leq i \leq N.
  • Pentru teste în valoare de 21 puncte N \leq 100.
  • Pentru alte teste în valoare de 28 de puncte N \leq 3000.
  • Se garantează că fiecare număr natural de la 1 la M apare cel puţin o dată.
  • Ultimul indice din fiecare soluţie va fi întotdeauna N.
  • În cazul în care există mai multe soluţii cu număr maxim de grupe stabile, se va afişa soluţia minimă lexicografic.
  • Un şir a_1, a_2, ..., a_n este mai mic lexicografic decât un alt şir b_1, b_2, ..., b_n dacă există un număr întreg P mai mic sau egal cu N astfel încât: a_1 = b_1, a_2 = b_2, ..., a_{P - 1} = b_{P - 1}, iar a_P < b_P.

Exemplu

compact3.incompact3.out
6 5
1 4 2 3 5 5
5
1 2 3 4 6
7 5
1 3 2 1 5 2 4
1
7
14 10
5 8 6 7 5 2 1 2 3 3 4 10 9 10
5
5 8 10 11 14
4 3
3 1 2 1
2
1 4
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?