問題一覧 > 教育的問題

No.3489 Making an Amidakuji

レベル : / AI推定難易度 : 700 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 42
作問者 : 👑 p-adic
お気に入りにしたユーザー ProblemId : 9066 / 自分の提出
問題文最終更新日: 2026-04-03 21:43:33
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 496 (順位表) の他の問題:

Problem Statement

You are given as input an integer $N$ greater than or equal to $2$ and a permutation $P$ of length $N$ consisting of positive integers less than or equal to $N$.

Determine whether there exists a vertically descending Amidakuji (ladder lottery) $A$ that satisfies all of the following conditions:

  1. $A$ has exactly $N$ vertical lines. (They are parallel to each other.)
  2. $A$ has at most $N^2$ horizontal lines. (They are perpendicular to the vertical lines, parallel to each other, and at pairwise distinct heights.)
  3. For every positive integer $i$ less than or equal to $N$, starting from the top of the $i$-th vertical line from the left of $A$ and following the lines downward according to the rules of Amidakuji, one reaches the bottom of the $P_i$-th vertical line from the left of $A$.

Here, $P_i$ denotes the $i$-th element of $P$.

Input

The input is given from Standard Input in $2$ lines in the following format:

  • Line $1$ contains $N$.
  • Line $2$ contains $P_i$ for each positive integer $i$ less than or equal to $N$, in increasing order of $i$, separated by single-byte spaces.
$N$
$P_1$ $\cdots$ $P_N$

Constraints

The input satisfies the following constraints:

  • $N$ is an integer satisfying $2 \leq N \leq 100$.
  • $P$ is a permutation of length $N$ consisting of positive integers less than or equal to $N$.

Output

If no Amidakuji $A$ satisfying the conditions exists, print No.

If one exists, choose $1$ such $A$. Let $M$ be the number of horizontal lines of $A$, and for each positive integer $j$ less than or equal to $M$, define the positive integer $i_j$ less than $N$ so that the $j$-th horizontal line from the top of $A$ connects the $i_j$-th vertical line from the left and the $i_j + 1$-th vertical line from the left of $A$. Print in the following format:

  • On line $1$, print Yes.
  • On line $2$, print $M$.
  • For each positive integer $j$ less than or equal to $M$, print $i_j$ on line $2 + j$.

Print a newline at the end.

Note that this is a special judge problem. There may be more than $1$ correct answer, but print only $1$ of them.

However, strictly follow the format described above. For example, the behavior of the judge is not guaranteed if there is extra whitespace.

Sample

Sample 1
Input
2
1 2
Output
Yes
0

An Amidakuji with $2$ vertical lines and $0$ horizontal lines satisfies the conditions. Other correct answers include

Yes
2
1
1

and so on. On the other hand, note that

Yes
6
1
1
1
1
1
1

is not correct. This example does not satisfy the condition that there are at most $N^2 = 4$ horizontal lines.

Sample 2
Input
2
2 1
Output
Yes
1
1

An Amidakuji with $2$ vertical lines and $1$ horizontal line, in which horizontal line number $1$ from the top connects vertical line number $1$ from the left and vertical line number $2$ from the left, satisfies the conditions.

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

The Amidakuji with $3$ vertical lines and $2$ horizontal lines obtained by setting

  • Horizontal line number $1$ from the top connects vertical line number $1$ from the left and vertical line number $2$ from the left.
  • Horizontal line number $2$ from the top connects vertical line number $2$ from the left and vertical line number $3$ from the left.

satisfies the conditions.

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