問題一覧 > 通常問題

No.2732 Similar Permutations

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

問題文

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

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

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

長さ NN の数列 (A1,A2,...,AN)(A_1, A_2, ..., A_N) に対し、⨁i=1NAi\bigoplus_{i=1}^{N} A_i を A1⊕A2⋯⊕ANA_1 \oplus A_2 \cdots \oplus A_N と定義します。

XOR ⊕\oplus とは

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

aa と bb の排他的論理和を a⊕ba \oplus bと表記します。

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

入力

NN  
A1 A2 ⋯ ANA_1\ A_2\ \cdots\ A_N
  • 入力はすべて整数である。
  • 1≦N≦2×1051 \leqq N \leqq2×10^5
  • 0≦Ai≦2×1050 \leqq A_i \leqq 2×10^5

出力

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


P1′ P2′ ⋯ PN′P'_1\ P'_2\ \cdots\ P'_N
P1′′ P2′′ ⋯ PN′′P''_1\ P''_2\ \cdots\ P''_N

サンプル

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

(1+1)⊕(2+1)⊕(3+2)=(3+1)⊕(2+1)⊕(1+2)(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もしくは右上の雲マークをクリックしてアカウントを作成してください。