双元素插入排序(Insertion Sort 2)

题目描述

$(1,2,\ldots,N)$ の順列 $P=(P_1,P_2,\ldots,P_N)$ が与えられます。

$P$ に対し以下の操作を $2\times\ 10^3$ 回以下行うことで $P$ を昇順に並び替えられるか判定し、可能な場合は実際に操作手順を一つ示してください。

• $1\leq\ i\ \leq\ N-1,0\ \leq\ j\ \leq\ N-2$ を満たす整数 $i,j$ を選ぶ。$Q\ =\ (Q_1,\ Q_2,\ldots,Q_{N-2})$ を $P$ から $(P_i,P_{i+1})$ を抜き出して得られる列としたとき、$P$ を $(Q_1,\ldots,Q_j,\ P_i,\ P_{i+1},\ Q_{j+1},\ldots,Q_{N-2})$ で置き換える。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $P_1$ $P_2$ $\ldots$ $P_N$

输出格式

$2\times\ 10^3$ 回以下の操作で $P$ を昇順に並び替えられない場合 No を出力せよ。昇順に並び替えられる場合、操作回数を $M\ (0\ \leq\ M\ \leq\ 2\times\ 10^3)$ とし、$k$ 回目 $(1\leq\ k\ \leq\ M)$ の操作で選んだ $i,j$ を $i_k,j_k$ として以下の形式で出力せよ。

Yes $M$ $i_1$ $j_1$ $i_2$ $j_2$ $\vdots$ $i_M$ $j_M$

条件を満たす解が複数存在する場合、どれを出力しても正解とみなされる。

样例输入 #1

5
1 4 2 3 5

样例输出 #1

Yes
1
3 1

样例输入 #2

2
2 1

样例输出 #2

No

样例输入 #3

4
3 4 1 2

样例输出 #3

Yes
3
3 0
1 2
3 0

数据范围

制約

• $2\ \leq\ N\ \leq\ 10^3$
• $P$ は $(1,2,\ldots,N)$ の順列
• 入力される数値は全て整数

Sample Explanation 1

$i=3,j=1$ として操作を行います。 $Q=(P_1,P_2,P_5)=(1,4,5)$ になるので、$P=(Q_1,P_3,P_4,Q_2,Q_3)\ =\ (1,2,3,4,5)$ となります。 よって $1$ 回の操作で $P$ を昇順に並び替えられます。

Sample Explanation 2

$2\times\ 10^3$ 回以下の操作では $P$ を昇順に並び替えられないことが証明できます。

Sample Explanation 3

操作回数を最小化する必要はありません。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1600。

测试点分布

出处：原题链接