分数: 500 点
问题陈述
排列 给出了 P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) 。
判断是否可以重新排列 最多执行以下操作按升序排列 P 最多执行以下操作按升序排列 2\times 10^3 次,如果可能的话,显示一个这样的操作序列。
- 选择整数 i 和 j 这样 1\leq i \leq N-1,0 \leq j \leq N-2。让 Q = (Q_1, Q_2,\ldots,Q_{N-2}) 是通过删除获得的序列 (P_i,P_{i+1}) 来自 P。更换 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
输出
If P 不能在以下时间内按升序重新排列 2\times 10^3 操作,打印 No。如果可以按升序重新排列,则令 M\ (0 \leq M \leq 2\times 10^3) 是操作次数,并且 i_k,j_k 被选中 i,j 为 k第次操作 (1\leq k \leq M),并按以下格式打印:
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).
因此, P 只需一次操作即可按升序重新排列。
示例输入 2
2 2 1
示例输出 2
No
可以证明 P 不能在以下时间内按升序重新排列 2\times 10^3 操作。
示例输入 3
4 3 4 1 2
示例输出 3
Yes 3 3 0 1 2 3 0
无需最小化操作次数。