Problem compact


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 ∉ [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

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 compact.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 poziţia ultimului element al fiecărei grupe stabile în ordine crescătoare.

Restricții

  • 1 ≤ N ≤ 1.000.000.
  • 1 ≤ M ≤ N.
  • 1 ≤ a[i] ≤ M, pentru 1 ≤ i ≤ N.
  • Pentru teste în valoare de 21 puncte N ≤ 100.
  • Pentru alte teste în valoare de 28 de puncte N ≤ 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\).
  • Precizare: 3 dintre teste nu au fost disponibile și au fost eliminate.

Exemplu

compact.in

6 5
1 4 2 3 5 5

compact.out

5
1 2 3 4 6

compact.in

7 5
1 3 2 1 5 2 4

compact.out

1
7

compact.in

14 10
5 8 6 7 5 2 1 2 3 3 4 10 9 10

compact.out

5
5 8 10 11 14

compact.in

4 3
3 1 2 1

compact.out

2
1 4

General info

ID: 12

Upload: liviu

Input: compact.in/compact.out

Memory limit: 128MB/8MB

Time limit: 0.6s

Author: Alex Tatomir

Source: ONI 2019 XI-XII: Ziua 2, Problema 1

Submissions

Special Submissions