/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
(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}) で置き換える。
制約
- 2 \leq N \leq 10^3
- P は (1,2,\ldots,N) の順列
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
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
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 を昇順に並び替えられます。
入力例 2
2 2 1
出力例 2
No
2\times 10^3 回以下の操作では P を昇順に並び替えられないことが証明できます。
入力例 3
4 3 4 1 2
出力例 3
Yes 3 3 0 1 2 3 0
操作回数を最小化する必要はありません。
Score : 500 points
Problem Statement
A permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) is given.
Determine whether it is possible to rearrange P in ascending order by performing the following operation at most 2\times 10^3 times, and if possible, show one such sequence of operations.
- Choose integers i and j such that 1\leq i \leq N-1,0 \leq j \leq N-2. Let Q = (Q_1, Q_2,\ldots,Q_{N-2}) be the sequence obtained by removing (P_i,P_{i+1}) from P. Replace P with (Q_1,\ldots,Q_j, P_i, P_{i+1}, Q_{j+1},\ldots,Q_{N-2}).
Constraints
- 2 \leq N \leq 10^3
- P is a permutation of (1,2,\ldots,N).
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N P_1 P_2 \ldots P_N
Output
If P cannot be rearranged in ascending order within 2\times 10^3 operations, print No. If it can be rearranged in ascending order, let M\ (0 \leq M \leq 2\times 10^3) be the number of operations, and i_k,j_k be the chosen i,j for the k-th operation (1\leq k \leq M), and print them in the following format:
Yes M i_1 j_1 i_2 j_2 \vdots i_M j_M
If there are multiple solutions, any of them will be considered correct.
Sample Input 1
5 1 4 2 3 5
Sample Output 1
Yes 1 3 1
Perform the operation with i=3,j=1.
Then, Q=(P_1,P_2,P_5)=(1,4,5), so you get P=(Q_1,P_3,P_4,Q_2,Q_3) = (1,2,3,4,5).
Thus, P can be rearranged in ascending order with one operation.
Sample Input 2
2 2 1
Sample Output 2
No
It can be proved that P cannot be rearranged in ascending order within 2\times 10^3 operations.
Sample Input 3
4 3 4 1 2
Sample Output 3
Yes 3 3 0 1 2 3 0
There is no need to minimize the number of operations.