#D. 在银河中孤独摇摆

    传统题 1000ms 512MiB

在银河中孤独摇摆

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

在银河中孤独摇摆 - 知更鸟 / HOYO-MiX / Chevy

题目描述

云浅给了你一个长为 nn 的排列 pp,你可以进行若干次操作,每次操作时,你可以先把序列任意划分成 kk 段(k2k\ge 2),每段都是原排列的一个非空子区间,且每个数恰好属于一段。设你分出的 kk 段分别为 p=A1+A2++Akp=A_1+A_2+\cdots+A_k(加法表示序列的拼接),那么这次操作会把排列 pp 变为 p=Ak+Ak1++A1p=A_k+A_{k-1}+\cdots+A_1

例如,p=(3,4,2,5,6,1,7)p=(3,4,2,5,6,1,7),你可以选择 k=4,A1=(3,4),A2=(2),A3=(5,6,1),A4=(7)k=4,A_1=(3,4),A_2=(2),A_3=(5,6,1),A_4=(7),然后操作之后 pp 会变为 Ak+Ak1++A1A_k+A_{k-1}+\cdots+A_1,即 (7,5,6,1,2,3,4)(7,5,6,1,2,3,4)

你需要在 120120 次操作内将排列排序为 1,2,,n1,2,\cdots,n。可以证明一定有解。

输入格式

第一行一个正整数 nn

第二行 nn 个正整数 p1,p2,,pnp_1,p_2,\cdots,p_n

输出格式

第一行一个非负整数 kk 表示操作次数。

接下来 kk 行,每行先输出一个正整数 mm 表示这次操作将序列划分出的段数,接下来同一行内输出 mm 个正整数 L1,L2,,LmL_1,L_2,\cdots,L_m 表示每段的长度。你需要保证 m2,L1+L2++Lm=nm\ge 2,L_1+L_2+\cdots+L_m=n

样例 11 输入

5
1 4 3 5 2

样例 11 输出

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

样例 11 解释

排列 pp 的变化为 $(1,4,3,5,2)\to (2,5,4,3,1)\to (3,1,2,5,4)\to (5,4,3,1,2)\to (1,2,3,4,5)$。

测试点约束

对于所有数据,保证 1n200001\le n\le 20000

子任务编号 nn\le 特殊性质 依赖子任务 分值
Subtask #1 88 77
Subtask #2 120120 11 2222
Subtask #3 240240 1,21,2 1010
Subtask #4 10001000 1,2,31,2,3 2929
Subtask #5 2000020000 A 1414
Subtask #6 1,2,3,4,5,61,2,3,4,5,6 1818

特殊性质 A:排列 pp 从所有 1,2,,n1,2,\cdots,n 的排列中均匀随机选取。

[YDRS#007] 无限风光在险峰 · 云斗五月 Silver Round

未参加
状态
已结束
规则
IOI(严格)
题目
5
开始于
2024-5-25 9:00
结束于
2024-5-25 20:00
持续时间
4 小时
主持人
参赛人数
105