#P13321. [2025年队测]兜兜转转

    ID: 12505 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>CF1900构造贪心模拟排序数学图论搜索

[2025年队测]兜兜转转

题目描述

wshcl 有一个长度为 nn 的排列。ET-G 将它随机打乱,你需要把它排成 1,2,…,n1,2,\ldots,n。

开始前指定一个固定整数 x∈[2,min⁡(n,1000)]x\in[2,\min(n,1000)]。之后可以使用以下两种操作:

  1. 兜兜转转。 给定 l∈[1,n−x+1]l\in[1,n-x+1],将区间 [l,l+x−1][l,l+x-1] 循环左移一位。原来位于 ll 的数移动到 l+x−1l+x-1,其余位置上的数向左移动一位。所有此类操作共用开始前选定的 xx。
  2. 交交换换。 给定 l∈[1,n−1]l\in[1,n-1],交换下标 ll 和 l+1l+1 上的数。

操作总次数不得超过 1.9×1061.9\times10^6。在此限制内将排列升序排序。得分取决于第 2 类操作的次数。

输入格式

第一行一个正整数 nn。

第二行 nn 个正整数,表示给出的排列。

输出格式

第一行输出两个整数 x,mx,m,分别表示选定的固定长度和操作总次数。允许 m=0m=0。

接下来 mm 行,每行两个整数,表示操作类型(11 或 22)及参数 ll。按输出顺序执行操作。

样例

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。此处采用原样例解释中能够完成排序的六步。

数据范围

对于全部数据,2≤n≤1.9×1042\le n\le1.9\times10^4,0≤m≤1.9×1060\le m\le1.9\times10^6。输入在 n!n! 种排列中等概率随机选取。

测试点 nn 的上限
1、2 25002500
3 70007000
4、5 10410^4
6、7、8 1.7×1041.7\times10^4
9、10 1.9×1041.9\times10^4

计分方式

记两类操作的次数分别为 m1,m2m_1,m_2。若没有将排列排成升序,或 m1+m2>1.9×106m_1+m_2>1.9\times10^6,该测试点不得分。否则按下表取满足条件的最高分。

每个测试点得分 1 2 3 4 5 6 10
条件 m2≤105m_2\le10^5 m2≤104m_2\le10^4 m2≤5000m_2\le5000 m2≤103m_2\le10^3 m2≤102m_2\le10^2 m2≤10m_2\le10 m2=0m_2=0

原题 PDF