P11084 [ROI 2019] Garland (Day 2)

Translated from [ROI 2019 D2T1](https://neerc.ifmo.ru/school/archive/2018-2019/ru-olymp-roi-2019-day2.pdf)。 For a sequence consisting of `0` and `1`, the definition of “beautiful” is: if the number of `0` before the first `1` equals the number of `0` after the last `1`, and the number of `0` between every two adjacent `1` is also equal to this value, then the sequence is called “beautiful”。 For example, `0101010` and `11111` are “beautiful”, but `10101` and `010100001000001010000` are not “beautiful”。

Given a sequence consisting of `0` and `1` (it is guaranteed that the number of `1` is not $0$), you need to delete some elements at arbitrary positions so that the remaining sequence forms the longest possible beautiful string.

The first line contains an integer $n$, the length of the sequence。 The second line contains a string $s$, consisting only of `0` and `1`, representing the sequence。

The first line outputs an integer $m$, the length of the remaining sequence after deletions。 The second line outputs the “beautiful” sequence that remains after the deletions。 If there are multiple solutions, output any one。**Note: a string consisting entirely of `0` is not “beautiful”。**

Suppose the original string has $k$ `1`s。 | Subtask | Score | $1\le n\le$ | $1\le k\le$ | | :----------: | :----------: | :----------: | :----------: | | $1$ | $20$ | $15$ | $n$ | | $2$ | $20$ | $1000$ | $2$ | | $3$ | $20$ | $1000$ | $15$ | | $4$ | $16$ | $1000$ | $n$ | | $5$ | $10$ | $100000$ | $50$ | | $6$ | $14$ | $500000$ | $n$ | Translated by ChatGPT 5