#P18936. [Mladen Manev 2019 A1] pancakesort / 煎饼排序

[Mladen Manev 2019 A1] pancakesort / 煎饼排序

煎饼排序(Pancake Sort)

题目描述

给定 1,2,…,N1,2,\ldots,N 的一个排列。一次操作选择一个整数 xx,将排列的前 xx 个元素整体翻转,后面的元素保持原位。

请输出一组操作,将排列变为 1,2,…,N1,2,\ldots,N。

输入格式

第一行一个整数 NN。第二行 NN 个整数,表示给定排列。

输出格式

第一行输出操作次数 MM,第二行输出 MM 个整数,依次表示每次翻转的前缀长度。每个长度必须在 [1,N][1,N] 内。

答案不唯一。获得该测试点全部分数需要 M≤⌊7N/3⌋M\le\lfloor 7N/3\rfloor。

数据范围

1≤N≤1000001\le N\le100000。

样例

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

计分与评测

原题对正确但操作较多的答案给部分分:当 7N/3<M≤13N/37N/3<M\le13N/3 时,比例为 (19/3−M/N)/4(19/3-M/N)/4;当 M>13N/3M>13N/3 时为 1/21/2。错误排序得零分。本包检查器保留这一单点规则,总分100;所有测试以一个捆绑子任务计分。

来源与数据说明

2019 年 Dr. Mladen Manev,A1,原题名 pancakesort。赛事资料,原文题面见附件 statement.pdf。

本题使用官方原始测试数据;评测接口按本站环境适配。总分为 100 分。