問題一覧 > 通常問題

No.2732 Similar Permutations

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 70
作問者 : kusirakusirakusirakusira / テスター : 👑 AngrySadEightAngrySadEight FplusFplusFFplusFplusF hiro1729hiro1729 🦠みどりむし🦠みどりむし
8 ProblemId : 10758 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-04-20 14:10:08

問題文

$(1, 2, ..., N)$ の順列の組 $P', P''$であって以下を満たすものがあるか判定し、存在する場合はその組をひとつ出力してください。

  • $\bigoplus_{i=1}^{N} \left( P'_i + A_i \right) = \bigoplus_{i=1}^{N} \left( P''_i + A_i \right)$
  • $P' \neq P''$
総XOR \(\bigoplus\) とは

\(\bigoplus\) は数列の指定された要素の総XORを示します。

長さ \(N\) の数列 \((A_1, A_2, ..., A_N)\) に対し、\(\bigoplus_{i=1}^{N} A_i\) を \(A_1 \oplus A_2 \cdots \oplus A_N\) と定義します。

XOR \(\oplus\) とは

XOR（排他的論理和）は、2つの要素間で行われる論理演算であり、同じビット位置において異なる場合に1を返し、同じ場合に0を返します。

$a$ と $b$ の排他的論理和を \(a \oplus b\)と表記します。

例えば、\(5 \oplus 3 = 6\) です。これは、\(101 \oplus 011 = 110\) というビットごとの操作によるものです。

入力

$N$  
$A_1\ A_2\ \cdots\ A_N$
  • 入力はすべて整数である。
  • $1 \leqq N \leqq2×10^5$
  • $0 \leqq A_i \leqq 2×10^5$

出力

題意を満たす順列の組が存在しない場合、-1を出力してください。
そうではない場合、1行目に $P'$ を2行目に $P''$ を以下の形式で出力してください。


$P'_1\ P'_2\ \cdots\ P'_N$
$P''_1\ P''_2\ \cdots\ P''_N$

サンプル

サンプル1
入力
3
1 1 2
出力
1 2 3
3 2 1

$(1+1) \oplus (2+1) \oplus (3+2) = (3+1) \oplus (2+1) \oplus (1+2)$ です。
また、 

2 1 3
3 2 1
などを出力しても正解となります。
サンプル2
入力
2
1 100
出力
-1

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