問題一覧 > 通常問題

No.3256 Permutation Equation

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 17
作問者 : Iroha_3856 / テスター : lif4635 champignon tikuwa_
ProblemId : 12617 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-09-05 19:36:05

問題文

正整数 $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$ と等しい
と、すべての $i$ について条件を満たすからです。

サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。