Blackslex and Penguin Civilization

Let $m=2^n$ and let

$A_i=p_0\&p_1\&\cdots\&p_i.$

We need maximize

$S(p)=\sum_{i=0}^{m-1}\operatorname{popcount}(A_i).$

The important move is to stop thinking about whole masks and split the score by bits.

Bit contribution

Fix a bit $b$. This bit contributes $1$ to $\operatorname{popcount}(A_i)$ exactly while every selected number $p_0,p_1,\ldots,p_i$ has bit $b$ equal to $1$.

The first time we choose a number with bit $b=0$, that bit disappears from the running AND forever. Bitwise AND is brutal like that.

Let $firstZero[b]$ be the first index $i$ such that bit $b$ of $p_i$ is $0$. Then bit $b$ contributes to exactly the prefixes

$0,1,\ldots,firstZero[b]-1,$

so it contributes $firstZero[b]$ total.

Therefore

$S(p)=\sum_{b=0}^{n-1} firstZero[b].$

So the job is: delay the first zero of every bit as much as possible.

Maximum possible score

The first element must be $2^n-1$, the all-ones mask. Otherwise some bit has first zero at index $0$, which is obviously worse, and no later number can bring that bit back.

After choosing $2^n-1$, every other number has at least one zero bit. As long as the current AND still has some alive bit, the next chosen number must kill at least one alive bit unless it has all those alive bits set.

But here is the catch: to keep the score as large as possible, we want to lose bits as slowly as possible. Losing two or more alive bits in one step is strictly worse than losing only one, because each dead bit stops contributing immediately.

There are only $n$ bits, and after the first element we can kill at least one new alive bit per useful step. So the best possible sequence of prefix popcounts is

$n, n-1, n-2, \ldots, 1, 0, 0, \ldots, 0.$

That gives maximum score

$n+(n-1)+\cdots+1=\frac{n(n+1)}2.$

This upper bound is achievable: pick masks whose running AND loses exactly one bit each time.

Lexicographically smallest optimal permutation

Now we need the lexicographically smallest sacred permutation.

The first value is forced:

$p_0=2^n-1.$

Suppose the currently alive bits form a mask alive. To stay optimal, the next number must kill exactly one alive bit. If it kills zero alive bits, we waste a position where the score could have dropped later incorrectly relative to the forced optimal shape; if it kills two or more alive bits, the score drops too fast. So during the first $n$ transitions, each next number must satisfy:

$\operatorname{popcount}(alive\ \&\ \sim x)=1.$

Among those valid unused choices, take the smallest $x$ to make the permutation lexicographically minimal.

What does that smallest choice look like?

Initially all bits are alive. To kill exactly one bit while making $x$ as small as possible, set the highest alive bit to $0$ and keep all lower alive bits as $1$. Bits that are already dead do not matter for optimality, so to make $x$ smaller, set them to $0$.

This gives the clean sequence:

$2^n-1,\;2^{n-1}-1,\;2^{n-2}-1,\;\ldots,\;1,\;0.$

Example for $n=4$:

$15,7,3,1,0.$

The running ANDs are exactly the same values, with popcounts

$4,3,2,1,0.$

After the running AND becomes $0$, every later prefix contributes $0$. So the remaining unused numbers have no effect on $S(p)$. For lexicographic minimum, just append them in increasing order.

That is the whole construction:

1. Output $(1<<n)-1$, then $(1<<(n-1))-1$, down to $0$.
2. Mark these as used.
3. Output every unused number from $0$ to $(1<<n)-1$ in increasing order.

Runtime is $O(2^n)$ per test case, which is exactly the output size. Can't beat printing the damn answer.