bzoj#P2386. [Ceoi2011]Team

[Ceoi2011]Team

题目描述

格丁尼亚一所小学将举办运动日,其中最重要的活动是年度足球杯赛。参赛的球队是赛前临时组建的。不难想象每个小选手都想加入到最好的球队中。

体育老师 Byteman 负责组织这项比赛。为了满足所有选手的愿望,他决定把这些选手按他们各自的意愿分到各个球队。第 ii 个选手(共 nn 个,编号 1n1\dots n)表示,如果球队少于 aia_i 个队员,他就不愿意留在这个球队。

除满足选手们的要求外,Byteman 希望球队的数目尽可能多。如果仍有多种选择,则要求人数最多的球队的队员人数尽可能少。这项任务难度不小,Byteman 需要你的帮助。

输入格式

第一行是整数 n(1n106)n(1\le n\le 10^6)。然后是 nn 行,其中第i行包括一个整数 ai(1ain)a_i(1\le a_i\le n),表示满足第 ii 个选手的球队的最少人数。

输出格式

第一行输出 11 个整数 tt,表示可能组建球队的最大数目。

接下来的 tt 行是对各个球队的描述,其中第 ii 行包含 11 个整数si(1sin)s_i(1\le s_i\le n),表示第 ii 个球队的人数,然后是 sis_i 个整数 $k_1,k_2,\dots,k_{s_i}(1\le k_j\le n,j=1,2,\dots,s_i)$, 表示属于第 ii 个球队的队员的编号。

样例输入

5
2
1
2
2
3

样例输出

2
2 4 2
3 5 1 3

数据规模与约定

对于所有数据,保证 1n106,1ain1\le n\le 10^6,1\le a_i\le n

至少 5050 分的测试数据,n5×103n\le 5\times 10^3