問題一覧 > 教育的問題

No.2089 Sign of a Permutation

レベル : / AI推定難易度 : 312 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 115
作問者 : 👑 p-adic / テスター : taiga0629kyopro
お気に入りにしたユーザー ProblemId : 8448 / 自分の提出
問題文最終更新日: 2022-09-30 21:03:37
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 362 (順位表) の他の問題:

Problem Statement

You are given as input an integer $N$ greater than or equal to $2$ and a permutation $A$ of degree $N$.

 

Find the sign of $A$.

 

Below is an explanation for those unfamiliar with permutations and their signs. (Click to expand)

 

For a positive integer $n$, a permutation of degree $n$ is, roughly speaking, a function that shuffles the positive integers less than or equal to $n$. More precisely, it is defined as follows:

 

Definition (Permutation)

Let $I_n$ be the set of all positive integers less than or equal to $n$. A permutation of degree $n$ is a bijective map from $I_n$ to $I_n$.

 

Let $n$ be an integer greater than or equal to $2$, and let $a$ be a permutation of degree $n$. Roughly speaking, $a$ being a transposition means that $a$ swaps exactly $2$ numbers. More precisely, it means that there exist positive integers $i$ and $j$ less than or equal to $n$ satisfying the following:

  1. $i \neq j$.
  2. $a(i) = j$.
  3. $a(j) = i$.
  4. For any positive integer $k$ less than or equal to $n$, if $k \neq i$ and $k \neq j$, then $a(k) = k$.

The sign of $a$ is an integer written $\textrm{sgn}(a)$, defined as follows:

  1. If $a$ can be expressed as a composition of an even number of transpositions, then $\textrm{sgn}(a) = 1$.
  2. If $a$ cannot be expressed as a composition of an even number of transpositions, then $\textrm{sgn}(a) = -1$.

Here, $0$ is an even number, and the composition of $0$ transpositions is defined as the identity permutation.

Input

The input is given from standard input in the following format:

$N$
$S$

Line $1$ contains $N$, and line $2$ contains the string $S$, which lists the image $A(i)$ of each positive integer $i$ less than or equal to $N$ under $A$, in increasing order of $i$, separated by half-width spaces.

In what follows, the $S$ obtained in this way is referred to as "the string representing $A$ in $1$-line notation".

Constraints

The input $N, S$ satisfies the following constraints:

  • $N$ is a non-negative integer between $2$ and $10^4$, inclusive
  • $S$ is a string representing a permutation of degree $N$ in $1$-line notation

Output

Output the sign of $A$ on $1$ line.

Print a newline at the end.

Sample

Sample 1
Input
2
1 2
Output
1

$A$ is the identity permutation $1 \ 2$. The identity permutation can be regarded as the composition of $0$ transpositions, and it is also the composition of $2$ copies of the transposition $2 \ 1$. In particular, $A$ can be expressed as a composition of an even number of transpositions.

Therefore, the sign of $A$ is $1$.

Sample 2
Input
2
2 1
Output
-1

$A$ is the transposition $2 \ 1$. The only transposition of degree $2$ is $A$ itself, and since $A \circ A$ is the identity permutation, any composition of an even number of copies of $A$ is the identity permutation. In particular, $A$, which is not the identity permutation, cannot be expressed as a composition of an even number of transpositions.

Therefore, the sign of $A$ is $-1$.

Sample 3
Input
3
3 1 2
Output
1

$A$ is the permutation $3 \ 1 \ 2$. The composition of the transpositions $3 \ 2 \ 1$ and $1 \ 3 \ 2$ in this order is

$\displaystyle 3 \ 2 \ 1 \circ 1 \ 3 \ 2 = 3 \ 1 \ 2 = A $

so, in particular, $A$ can be expressed as a composition of an even number of transpositions.

Therefore, the sign of $A$ is $1$.

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