D - And is 0
Editorial
/ 
一般に k 個の整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{AND} は (\dots ((p_1\ \mathrm{AND}\ p_2)\ \mathrm{AND}\ p_3)\ \mathrm{AND}\ \dots\ \mathrm{AND}\ p_k) と定義され、これは p_1, p_2, p_3, \dots p_k の順番によらないことが証明できます。
/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
整数 N が与えられます．
非負整数列 A=(A_1,A_2,\cdots,A_k) であって，以下の条件を満たすものが存在するか判定してください． また，存在するならば実際に一つ示してください．
- A の長さ k は 1 以上 100 以下である．
- A の各要素は 0 以上 2^{20}-1 以下の整数である．
- A の非空な（連続するとは限らない）部分列であって，その値のビット単位 \mathrm{AND} が 0 になるものを考える． そのような部分列の個数はちょうど N 個である． ただしここで，取り出す位置が異なる 2 つの部分列は，値が同じであったとしても異なるものとして扱う．
ビット単位 \mathrm{AND} 演算とは
整数 A, B のビット単位 \mathrm{AND}、A\ \mathrm{AND}\ B は以下のように定義されます。
- A\ \mathrm{AND}\ B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち両方が 1 であれば 1、そうでなければ 0 である。
一般に k 個の整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{AND} は (\dots ((p_1\ \mathrm{AND}\ p_2)\ \mathrm{AND}\ p_3)\ \mathrm{AND}\ \dots\ \mathrm{AND}\ p_k) と定義され、これは p_1, p_2, p_3, \dots p_k の順番によらないことが証明できます。
制約
- 1 \leq N \leq 2 \times 10^5
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる．
N
出力
条件を満たす数列 A が存在しない場合，-1 と出力せよ．
存在する場合，以下の形式で出力せよ．
k A_1 A_2 \cdots A_k
条件をみたす解が複数存在する場合，どれを出力しても正解とみなされる．
入力例 1
3
出力例 1
3 2 1 1
A の非空な部分列であって，その値のビット単位 \mathrm{AND} が 0 になるものは，以下の 3 つです．
- (2,1) (1,2 番目の要素を取り出した)
- (2,1) (1,3 番目の要素を取り出した)
- (2,1,1) (1,2,3 番目の要素を取り出した)