#P13321. [2025年队测]兜兜转转
[2025年队测]兜兜转转
题目描述
wshcl 有一个长度为 的排列。ET-G 将它随机打乱,你需要把它排成 。
开始前指定一个固定整数 。之后可以使用以下两种操作:
- 兜兜转转。 给定 ,将区间 循环左移一位。原来位于 的数移动到 ,其余位置上的数向左移动一位。所有此类操作共用开始前选定的 。
- 交交换换。 给定 ,交换下标 和 上的数。
操作总次数不得超过 。在此限制内将排列升序排序。得分取决于第 2 类操作的次数。
输入格式
第一行一个正整数 。
第二行 个正整数,表示给出的排列。
输出格式
第一行输出两个整数 ,分别表示选定的固定长度和操作总次数。允许 。
接下来 行,每行两个整数,表示操作类型( 或 )及参数 。按输出顺序执行操作。
样例
6
6 1 3 5 2 4
3 6
1 3
1 1
1 3
1 2
1 4
1 4
依次得到以下排列:
6 1 3 5 2 4
6 1 5 2 3 4
1 5 6 2 3 4
1 5 2 3 6 4
1 2 3 5 6 4
1 2 3 6 4 5
1 2 3 4 5 6
原 PDF 的样例输出多写了一次 1 3。此处采用原样例解释中能够完成排序的六步。
数据范围
对于全部数据,,。输入在 种排列中等概率随机选取。
| 测试点 | 的上限 |
|---|---|
| 1、2 | |
| 3 | |
| 4、5 | |
| 6、7、8 | |
| 9、10 |
计分方式
记两类操作的次数分别为 。若没有将排列排成升序,或 ,该测试点不得分。否则按下表取满足条件的最高分。
| 每个测试点得分 | 1 | 2 | 3 | 4 | 5 | 6 | 10 |
|---|---|---|---|---|---|---|---|
| 条件 |