301954: CF370E. Summer Reading
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Summer Reading
题意翻译
给你一个长度为 $n(2 \le n \le 2 \cdot 10^5)$ 的数列 $a_1, a_2, \ldots, a_n(0 \le a_i \le 10^5)$,你需要修改数列中所有数值为 $0$ 的那些数的值,使最终的数列满足: - $a_1 = 1$; - 对于任意 $i \gt 1$,$a_i = a_{i-1}$ 或者 $a_i = a_{i-1} + 1$; - 数列中具有相同数值的数的个数至少为 $2$ 至多为 $5$(即:如果数列中存在一个元素的数值为 $x$,则数列中数值为 $x$ 的元素最少有 $2$ 个,最多有 $5$ 个); - $a_n$ 尽可能地大。 请输出一个满足上述条件的数列。如果存在多种情况,输出其中任意一种即可。题目描述
At school Vasya got an impressive list of summer reading books. Unlike other modern schoolchildren, Vasya loves reading, so he read some book each day of the summer. As Vasya was reading books, he was making notes in the Reader's Diary. Each day he wrote the orderal number of the book he was reading. The books in the list are numbered starting from 1 and Vasya was reading them in the order they go in the list. Vasya never reads a new book until he finishes reading the previous one. Unfortunately, Vasya wasn't accurate and some days he forgot to note the number of the book and the notes for those days remained empty. As Vasya knows that the literature teacher will want to check the Reader's Diary, so he needs to restore the lost records. Help him do it and fill all the blanks. Vasya is sure that he spends at least two and at most five days for each book. Vasya finished reading all the books he had started. Assume that the reading list contained many books. So many, in fact, that it is impossible to read all of them in a summer. If there are multiple valid ways to restore the diary records, Vasya prefers the one that shows the maximum number of read books.输入输出格式
输入格式
The first line contains integer $ n $ — the number of summer days ( $ 2<=n<=2·10^{5} $ ). The second line contains $ n $ integers $ a_{1},a_{2},...\ a_{n} $ — the records in the diary in the order they were written ( $ 0<=a_{i}<=10^{5} $ ). If Vasya forgot to write the number of the book on the $ i $ -th day, then $ a_{i} $ equals 0.
输出格式
If it is impossible to correctly fill the blanks in the diary (the diary may contain mistakes initially), print "-1". Otherwise, print in the first line the maximum number of books Vasya could have read in the summer if we stick to the diary. In the second line print $ n $ integers — the diary with correctly inserted records. If there are multiple optimal solutions, you can print any of them.
输入输出样例
输入样例 #1
7
0 1 0 0 0 3 0
输出样例 #1
3
1 1 2 2 3 3 3
输入样例 #2
8
0 0 0 0 0 0 0 0
输出样例 #2
4
1 1 2 2 3 3 4 4
输入样例 #3
4
0 0 1 0
输出样例 #3
1
1 1 1 1
输入样例 #4
4
0 0 0 3
输出样例 #4
-1