No.3256 Permutation Equation
タグ : / 解いたユーザー数 21
作問者 :
Iroha_3856
/ テスター :
lif4635
champignon
tikuwa_
問題文
正整数 $N$ と、$(1, 2, \ldots, N)$ の順列 $P = (P_1, P_2, \ldots, P_N)$ が与えられます。
$(1, 2, \ldots, N)$ の順列 $Q = (Q_1, Q_2, \ldots, Q_N)$ であって、$i = 1, 2, \ldots, N$ について、$P_i = Q_{Q_i \textcolor{red}{ + 1}}$ が成立するものを一つ出力してください。ただし、$Q_{N+1} = Q_1$ であるとします。
そのような $Q$ が存在しない場合は、そのことを報告してください。
入力
$N$ $P_1\ P_2\ \ldots\ P_N$
入力は全て以下の制約を満たす
- $1 \leq N \leq 2 \times 10^5$
- $P$ は $(1, 2, \ldots, N)$ の順列
- 入力は全て整数
出力
条件を満たす $Q$ が存在する場合は
Yes $Q_1\ Q_2\ \ldots\ Q_N$と出力し、最後に改行してください。
条件を満たす $Q$ が存在しない場合は、
Noと出力し、最後に改行してください。
サンプル
サンプル1
入力
4 3 1 4 2
出力
Yes 2 1 3 4
$Q = (2, 1, 3, 4)$ は解のうち一つです。
- $P_1 = 3$ は $Q_{Q_1 + 1} = Q_{3} = 3$ と等しい
- $P_2 = 1$ は $Q_{Q_2 + 1} = Q_{2} = 1$ と等しい
- $P_3 = 4$ は $Q_{Q_3 + 1} = Q_{4} = 4$ と等しい
- $P_4 = 2$ は $Q_{Q_4 + 1} = Q_{5} = Q_{1} = 2$ と等しい
サンプル2
入力
6 4 2 6 1 5 3
出力
No
条件を満たす $Q$ は存在しません。
サンプル3
入力
7 6 5 1 3 7 2 4
出力
Yes 1 6 7 3 2 4 5
条件を満たす $Q$ は $(1, 6, 7, 3, 2, 4, 5), (2, 4, 6, 3, 5, 7, 1), (4, 2, 5, 3, 6, 1, 7), (5, 7, 4, 3, 1, 6, 2)$ の $4$ つです。
このうちどれかを出力すれば正解となります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。