[ROI 2018] Quick sort

Luogu

IDLGP9291

Time1000ms

Memory512MB

DifficultyP6

2018Special JudgeROI（俄罗斯）

给一个包含 $n$ 个元素的排列 $[a_1,a_2,\ldots,a_n]$。定义操作 $S(l,r),$ 表示：将数列的片段 $[a_l,a_{l+1},\ldots,a_r]$ 重排成 $[a_{l+1},a_{l+3},\ldots,a_l,a_{l+2},\ldots]$。举个例子：$[2, 4, 1, 5, 3, 6, 7, 8]\xrightarrow{S(2,6)} [2, 1, 3, 4, 5, 6, 7, 8]$，其中子串 $[4, 1, 5, 3, 6]$ 被重排成了 $[1, 3, 4, 5, 6]$。给定一个排列，试求经过多少次操作能使排列变成递增顺序，并输出任意一组方案，$不$要求方案的操作次数最少，但要求操作次数 $\leq 15000$。 ## Input 第一行一个数 $n$。第二行 $n$ 个数，表示排列 $a$。 ## Output 第一行一个整数 $k$，表示你的操作次数。需要满足 $0 \leq k \leq 15000$。接下来 $k$ 行，你需要按照操作顺序描述你的操作。对于每一步操作，输出两个数 $L$, $R$，表示你对片段 $a_L,a_{L+1},\ldots, a_R$ 执行了一次操作。需满足 $1 \leq L \leq R \le n$。注意，你**不**需要最小化。你只需保证 $0 \le k \leq 15000$ 即可。保证存在这样的 $k$。 [samples] ## Background 译自 [ROI 2018 Day2](https://neerc.ifmo.ru/school/archive/2017-2018.html) T2. [Быстрая сортировка ](https://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-day2.pdf)([Quick sort](http://codeforces.com/gym/102154/problem/C))。 ## Note 此处设 $k_0$ 表示最小操作次数。对于所有数据，$1\leq n\leq 3000$，$0\leq k_0\leq 15000$，$1\leq a_i\leq n$，且 $a_i$ 互不相同。 | 子任务编号 | $n$ | 特殊性质 | | :-----------: | :-----------: | :-----------: | | $1$ | $1 \leq n \leq 100$ | $k_0 = 1$ | | $2$ | $1 \leq n \leq 100$ | 无 | | $3$ | $1 \leq n \leq 1000$ | 无 | | $4$ | $1 \leq n \leq 3000$ | 无 |

Samples

Input #1

5
3 1 4 2 5

Output #1

1
1 5

Input #2

8
2 4 1 5 3 6 7 8

Output #2

2
2 6
1 2

Input #3

2
2 1

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[ROI 2018] Quick sort",
    "description": {
      "content": "给一个包含 $n$ 个元素的排列 $[a_1,a_2,\\ldots,a_n]$。 定义操作 $S(l,r),$ 表示：将数列的片段 $[a_l,a_{l+1},\\ldots,a_r]$ 重排成 $[a_{l+1},a_{l+3},\\ldots,a_l,a_{l+2},\\ldots]$。 举个例子：$[2, 4, 1, 5, 3, 6, 7, 8]\\xrightarrow{S(2,6)} [2, 1",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9291"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给一个包含 $n$ 个元素的排列 $[a_1,a_2,\\ldots,a_n]$。\n定义操作 $S(l,r),$ 表示：将数列的片段 $[a_l,a_{l+1},\\ldots,a_r]$ 重排成 $[a_{l+1},a_{l+3},\\ldots,a_l,a_{l+2},\\ldots]$。\n举个例子：$[2, 4, 1, 5, 3, 6, 7, 8]\\xrightarrow{S(2,6)} [2, 1...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments