Background

Translated from Izborne Pripreme 2021 (Croatian IOI/CEOI Team Selection) D1T1。$\texttt{1s,0.5G}$。

Due to the special SPJ of this problem, the TL and ML of this problem are changed to $\texttt{10s,2G}$ respectively. However, for contestants' programs, the time and memory limits are the same as in the original problem.

If you upload your answer using a zip package, name the files as $\texttt{jelo-1.out}\sim \texttt{jelo-5.out}$ respectively.

Problem Description

Given a positive even integer $N$, construct a largest possible set $S\subseteq \{0,1,\cdots,2^{N}-1\}$ such that $\left|\bigcup_{i,j\in S,i\lt j} \{i\oplus j\}\right|={|S|\choose 2}$。In other words, for any two chosen pairs $(a,b),(c,d)$ in $S$ ($a,b,c,d\in S$, $a\lt b$, $c\lt d$, $(a,b)\neq (c,d)$), it holds that $a\oplus b\neq c\oplus d$.

Here, $\oplus$ denotes the bitwise XOR operation.

Input Format

One line containing a positive integer $N$.

Output Format

The first line contains an integer $|S|$.

Then output $|S|$ numbers describing $S$.

4

6
0 1 2 4 8 15

Hint

For $100\%$ of the testdata, it is guaranteed that $1\le N\le 30$.

This problem has $5$ test points. Each test point has three scoring parameters $t_1,t_2,t_3$. Let $t=|S|$. The score is computed as:

$$\mathrm{score}(t)= \begin{cases} 2.4\cdot \frac{t}{t_1} & t\in [0,t_1) \\ 2.4+3.6\cdot \frac{t-t_1}{t_2-t_1} & t\in [t_1,t_2) \\ 6+12\cdot \frac{t-t_2}{t_3-t_2} & t\in [t_2,t_3) \\ 20 & t\in [t_3,2^N] \\ \end{cases}$$

Test Point ID	$N=$	$t_1=$	$t_2=$	$t_3=$	Score
$1$	$18$	$267$	$283$	$512$	$20$
$2$	$20$	$444$	$462$	$1024$
$3$	$26$	$2019$	$2040$	$8192$
$4$	$28$	$3295$	$3327$	$16384$
$5$	$30$	$5377$	$5430$	$32768$

[Hint] Please pay attention to the code length limit.

Translated by ChatGPT 5