← 返回题目列表

Codeforces · 1170/D

D. 整数序列的解码

中文机器翻译题面 查看原题

Polycarp 正在开发一种通过网络传输 $$$n$$$ 整数序列的方法。该方法应该支持传输任意数量的整数序列;序列可以有不同的长度。该序列包含任意非负整数。

Polycarp 开发了以下编码程序:

- 我们假设序列的编号从 $$$1$$$ 到 $$$n$$$。
- 我们在每个序列的末尾添加一个特殊的终止标记,该元素等于 -1。
- 编码结果是一个新的单个序列,其中包含指定 $$$n$$$ 的所有元素,按特殊顺序:首先,将序列的所有第一个元素(按照从 $$$1$$$-st 到 $$$n$$$-th 的顺序)添加到编码结果中,然后将所有第二个元素(按照从 $$$1$$$-st 到 $$$n$$$-th 的顺序)添加到编码结果中上,如果序列没有相应的元素,则简单地跳过。当添加所有序列的所有元素时,该过程结束。

例如,如果要对三个序列 $$$[3, 1, 4]$$$、$$$[2, 7]$$$ 和 $$$[1, 2, 3, 4]$$$ 进行编码,则操作顺序如下:

- 我们通过附加 -1 来修改所有三个序列:$$$[3, 1, 4, -1]$$$、$$$[2, 7, -1]$$$ 和 $$$[1, 2, 3, 4, -1]$$$;
- 我们写出所有第一个元素,我们得到 $$$[3, 2, 1]$$$;
- 然后写下所有第二个元素,我们得到$$$[3, 2, 1, 1, 7, 2]$$$;
- 然后写下所有第三个元素,我们得到$$$[3, 2, 1, 1, 7, 2, 4, -1, 3]$$$;
- 然后写下所有第四个元素,得到$$$[3, 2, 1, 1, 7, 2, 4, -1, 3, -1, 4]$$$(注意第二个序列已经结束);
- 然后写下所有第五个元素,我们得到$$$[3, 2, 1, 1, 7, 2, 4, -1, 3, -1, 4, -1]$$$(注意第一和第二序列已经结束);
- 所有序列现已结束,编码过程完成;
- 编码结果为:$$$[3, 2, 1, 1, 7, 2, 4, -1, 3, -1, 4, -1]$$$。

你的任务是根据给定的编码结果实现解码。

输入

第一行是整数$$$m$$$ ($$$1 \le m \le 3\cdot10^5$$$),表示编码结果的长度。第二行包含编码为整数序列 $$$b_1, b_2, \dots, b_m$$$ ($$$-1 \le b_i \le 100$$$) 的结果。

保证在编码前的初始序列中仅包含从 $$$0$$$ 到 $$$100$$$ 的非负整数,您实际上得到了正确编码的结果(换句话说,保证答案存在)。编码前一个或多个初始序列可能为空。

输出

打印 $$$n$$$,其中 $$$n$$$ 是编码序列的数量。然后以 $$$k_i, a_{i1}, a_{i2}, \dots, a_{ik_i}$$$ 格式打印 $$$n$$$ 行,其中 $$$k_i$$$ 是第 $$$i$$$ 序列的长度,$$$a_{i1}, a_{i2}, \dots, a_{ik_i}$$$ 是其元素。行中的数字用空格分隔。请注意,编码过程使得每种可能的编码结果只能以一种方式解码。

示例

输入 #1

12
3 2 1 1 7 2 4 -1 3 -1 4 -1

输出 #1

3
3 3 1 4
2 2 7
4 1 2 3 4

输入 #2

6
2 -1 2 -1 3 -1

输出 #2

3
1 2
0
2 2 3