codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1628A.md (2773B)


      1 Source: https://codeforces.com/problemset/problem/1628/A
      2 
      3 A. Meximum Array
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Mihai has just learned about the [MEX](https://en.wikipedia.org/wiki/Mex_(mathematics)) concept and since he liked it so much, he decided to use it right away.
     22 
     23 Given an array $a$ of $n$ non-negative integers, Mihai wants to create a new array $b$ that is formed in the following way:
     24 
     25 While $a$ is not empty:
     26 
     27 * Choose an integer $k$ ($1 \leq k \leq |a|$).
     28 * Append the MEX of the first $k$ numbers of the array $a$ to the end of array $b$ and erase them from the array $a$, shifting the positions of the remaining numbers in $a$.
     29 
     30 But, since Mihai loves big arrays as much as the MEX concept, he wants the new array $b$ to be the lexicographically maximum. So, Mihai asks you to tell him what the maximum array $b$ that can be created by constructing the array optimally is.
     31 
     32 An array $x$ is lexicographically greater than an array $y$ if in the first position where $x$ and $y$ differ $x_i \gt y_i$ or if $|x| \gt |y|$ and $y$ is a prefix of $x$ (where $|x|$ denotes the size of the array $x$).
     33 
     34 The MEX of a set of non-negative integers is the minimal non-negative integer such that it is not in the set. For example, MEX({${1, 2, 3}$}) $= 0$ and MEX({${0, 1, 2, 4, 5}$}) $= 3$.
     35 
     36 Input
     37 
     38 The first line of the input contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. The description of test cases follows.
     39 
     40 The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of elements in the array $a$.
     41 
     42 The second line of each test case contains $n$ non-negative integers $a_1, \ldots, a_n$ ($0 \leq a_i \leq n$), where $a_i$ is the $i$-th integer from the array $a$.
     43 
     44 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     45 
     46 Output
     47 
     48 For each test case print $m$ — the length of the maximum array $b$ Mihai can create, followed by $m$ integers denoting the elements of the array $b$.
     49 
     50 Example
     51 
     52 Input
     53 
     54 ```
     55 6
     56 
     57 5
     58 
     59 1 0 2 0 3
     60 
     61 8
     62 
     63 2 2 3 4 0 1 2 0
     64 
     65 1
     66 
     67 1
     68 
     69 5
     70 
     71 0 1 2 3 4
     72 
     73 4
     74 
     75 0 1 1 0
     76 
     77 10
     78 
     79 0 0 2 1 1 1 0 0 1 1
     80 ```
     81 
     82 Output
     83 
     84 ```
     85 1
     86 4 
     87 2
     88 5 1 
     89 1
     90 0 
     91 1
     92 5 
     93 2
     94 2 2 
     95 4
     96 3 2 2 0
     97 ```
     98 
     99 Note
    100 
    101 In the first test case, the lexicographically maximum array $b$ is obtained by selecting $k=5$, resulting in the $MEX$ of the whole array $a$. It is lexicographically maximum because an array starting with a smaller number than $4$ is lexicographically smaller, and choosing a $k \lt 5$ would result in an array starting with a number smaller than $4$.
    102 
    103 In the second test case, there are two ways to obtain the maximum array: first selecting $k=6$, then $k=2$, or first selecting $k=7$ and then $k=1$.