問題一覧 > 通常問題

No.3256 Permutation Equation

レベル : / AI推定難易度 : 1800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : （AC するまで非表示） / 解いたユーザー数 22
作問者 : Iroha_3856 / テスター : lif4635 champignon tikuwa_
お気に入りにしたユーザー ProblemId : 12617 / 自分の提出
問題文最終更新日: 2025-09-05 19:36:05
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 481 菁々祭プログラミングコンテスト2025 (順位表) の他の問題:

Problem Statement

You are given a positive integer $N$ and a permutation $P = (P_1, P_2, \ldots, P_N)$ of $(1, 2, \ldots, N)$.

Output one permutation $Q = (Q_1, Q_2, \ldots, Q_N)$ of $(1, 2, \ldots, N)$ such that $P_i = Q_{Q_i \textcolor{red}{ + 1}}$ holds for $i = 1, 2, \ldots, N$. Here, we assume that $Q_{N+1} = Q_1$.

If no such $Q$ exists, report that fact.

Input

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

All inputs satisfy the following constraints.

  • $1 \leq N \leq 2 \times 10^5$
  • $P$ is a permutation of $(1, 2, \ldots, N)$
  • All inputs are integers

Output

If a $Q$ satisfying the condition exists, output 

Yes
$Q_1\ Q_2\ \ldots\ Q_N$
followed by a newline.

If no $Q$ satisfying the condition exists, output

No
followed by a newline.

Sample

Sample 1
Input
4
3 1 4 2
Output
Yes
2 1 3 4

$Q = (2, 1, 3, 4)$ is one of the solutions.

  • $P_1 = 3$ is equal to $Q_{Q_1 + 1} = Q_{3} = 3$
  • $P_2 = 1$ is equal to $Q_{Q_2 + 1} = Q_{2} = 1$
  • $P_3 = 4$ is equal to $Q_{Q_3 + 1} = Q_{4} = 4$
  • $P_4 = 2$ is equal to $Q_{Q_4 + 1} = Q_{5} = Q_{1} = 2$
Thus, the condition is satisfied for all $i$.

Sample 2
Input
6
4 2 6 1 5 3
Output
No

No $Q$ satisfying the condition exists.

Sample 3
Input
7
6 5 1 3 7 2 4
Output
Yes
1 6 7 3 2 4 5

There are $4$ permutations $Q$ satisfying the condition: $(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)$.

Outputting any of these will be judged as correct.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。