No.482 Your Name Is
タグ : / 解いたユーザー数 285
作問者 :
ei1333333
/ テスター :
tatuyan_edson
Problem Statement
There are $N$ people, numbered from $1$ to $N$. Initially, person $i$ was inhabited by their own soul $i$.
Hakubishin-kun is a pro, so he can perform an operation of choosing any $2$ distinct people and swapping the souls inhabiting those $2$ people. Absorbed in this operation, Hakubishin-kun performed it several times. As a result, person $i$ is currently inhabited by soul $D_i$.
Now Hakubishin-kun has realized that after $K$ more soul-swapping operations, he will lose his ability to perform the operation.
Since it would be cruel to leave people inhabited by souls other than their own, he wants to return to the initial state, in which every person is inhabited by their own soul.
Also, if any of his ability remains, he might give in to the urge to use it, so he wants to use up exactly $K$ operations.
Determine whether it is possible to return to the state in which every person is inhabited by their own soul using exactly $K$ operations.
Input
$N\ K$ $D_1\ D_2\ \dots\ D_N$
- The $1$st line contains the number of people $N(2 \le N \le 200\ 000)$ and the number of remaining operations $K(1 \le K \le 10^{12}) $.
- The $2$nd line gives the current state of the souls. The $i(1 \le i \le N)$-th value $D_i(1 \le D_i \le N)$ means that person $i$ is currently inhabited by soul $D_i$. It is guaranteed that each value from $1$ to $N$ appears exactly $1$ time.
Note that $K$ may not fit in a 32 bit integer type.
Output
Print YES on $1$ line if it is possible to make every person inhabited by their own soul using exactly $K$ operations,
and NO if it is not possible.
Print a newline at the end.
Sample
Sample 1
Input
2 1 2 1
Output
YES
Exactly $1$ operation is performed.
Choosing person $1$ and person $2$ and swapping their souls gives $\{1, 2\}$, and every person is inhabited by their own soul, so print
YES.
Sample 2
Input
3 2 3 2 1
Output
NO
With exactly $2$ operations, it is not possible to make every person inhabited by their own soul.
Print NO.
For example, choosing person $1$ and person $3$ and swapping their souls gives $\{1, 2, 3\}$, but $2$ operations must be performed.
Sample 3
Input
4 2 1 2 3 4
Output
YES
For example, choosing person $1$ and person $2$ in the $1$st operation and swapping their souls gives $\{2, 1, 3, 4\}$.
Choosing person $1$ and person $2$ again in the $2$nd operation and swapping their souls gives $\{1, 2, 3, 4\}$, so print YES.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。