ゆるふわ競技プログラミングオンサイト at FORCIA #9
コンテスト日時
2026/11/07 (Sa) 14:15 - 16:45

F - Maximum Zero Xor Prefixes

Darjeeling
2
s
1024
MB
600
点

問題文

正の整数 $N$ が与えられます。$M=2^N-1$ とします。

$1,2,\ldots,M$ を並べ替えた順列 $P=(P_1,P_2,\ldots,P_M)$ を考えます。
各整数 $i$($1\leq i\leq M$)について、

$Q_i=P_1\oplus P_2\oplus\cdots\oplus P_i$

と定めます。ここで、$\oplus$ は整数のビットごとの排他的論理和(XOR)を表します。

$Q_i=0$ を満たす $i$ の個数が最大となる順列 $P$ を1つ求めてください。

制約

  • $2\leq N\leq18$
  • 入力は整数である。

入力

入力は以下の形式で標準入力から与えられます。

$N$

出力

求めた順列 $P$ の要素を、以下の形式で空白区切りで 1 行に出力してください。

$P_1 \space P_2 \space \ldots \space P_M$

出力する整数は $1,2,\ldots,M$ をそれぞれちょうど 1 回ずつ含む必要があります。
条件を満たす順列が複数存在する場合は、どれを出力しても正解となります。

入力例 1
2
出力例 1
2 3 1

この出力では $Q=(2,1,0)$ となり、$Q_i=0$ を満たす $i$ の個数は1です。これが最大です。

他にも、$(1,3,2)$ などを出力しても、$Q = (1,2,0)$ で、 $Q_i = 0$ を満たす $i$ が1個で最大となり、正解となります。

入力例 2
3
出力例 2
4 1 6 3 7 2 5
提出
C++23 (g++ 12.2.0)