No.2732 Similar Permutations
タグ : / 解いたユーザー数 72
作問者 :
kusirakusira
/ テスター :
👑 
FplusFplusF
hiro1729
みどりむし🦠
Problem Statement
Determine whether there exists a pair $P', P''$ of permutations of $(1, 2, ..., N)$ satisfying the following conditions, and if one exists, output one such pair.
- $\bigoplus_{i=1}^{N} \left( P'_i + A_i \right) = \bigoplus_{i=1}^{N} \left( P''_i + A_i \right)$
- $P' \neq P''$
What is the total XOR \(\bigoplus\)?
\(\bigoplus\) denotes the total XOR of the specified elements of a sequence.
For a sequence \((A_1, A_2, ..., A_N)\) of length \(N\), \(\bigoplus_{i=1}^{N} A_i\) is defined as \(A_1 \oplus A_2 \cdots \oplus A_N\).
What is XOR \(\oplus\)?
XOR (exclusive OR) is a logical operation performed between two elements that returns 1 if the bits at the same position differ and 0 if they are the same.
The exclusive OR of $a$ and $b$ is written as \(a \oplus b\).
For example, \(5 \oplus 3 = 6\). This follows from the bitwise operation \(101 \oplus 011 = 110\).
Input
$N$ $A_1\ A_2\ \cdots\ A_N$
- All inputs are integers.
- $1 \leqq N \leqq2×10^5$
- $0 \leqq A_i \leqq 2×10^5$
Output
If no pair of permutations satisfying the conditions exists, output -1.
Otherwise, output $P'$ on the first line and $P''$ on the second line in the following format.
$P'_1\ P'_2\ \cdots\ P'_N$ $P''_1\ P''_2\ \cdots\ P''_N$
Sample
Sample 1
Input
3 1 1 2
Output
1 2 3 3 2 1
We have $(1+1) \oplus (2+1) \oplus (3+2) = (3+1) \oplus (2+1) \oplus (1+2)$.
Also, outputs such as
2 1 3 3 2 1are also accepted.
Sample 2
Input
2 1 100
Output
-1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。