MEXOR

The evolving MEX looks annoying, but for a permutation it is really just a suffix minimum wearing a fake mustache.

From MEX to suffix minima

Fix an index $i<n-1$. The prefix and the remaining suffix partition all values $0,1,\ldots,n-1$. Therefore, the values from this range that are absent from the prefix are exactly $p_{i+1},p_{i+2},\ldots,p_{n-1}.$ The suffix is nonempty, so its minimum is at most $n-1$ and appears before any missing value $n,n+1,\ldots$. Hence $f(i)=\min(p_{i+1},p_{i+2},\ldots,p_{n-1}).$

For the complete permutation, every value from $0$ through $n-1$ is present, so $f(n-1)=n.$

Now reverse the permutation. Define $a_j=p_{n-1-j}$ and let $q_j=\min(a_0,a_1,\ldots,a_j)$ be the prefix minima of $a$.

Every nonempty suffix of $p$ is a prefix of $a$. As $i$ ranges from $0$ to $n-2$, the suffix minima above become exactly $q_0,q_1,\ldots,q_{n-2}$, only in the opposite order. XOR does not care about order, so the total is

$$\bigoplus_{i=0}^{n-1} f(i) = n\oplus\bigoplus_{j=0}^{n-2}q_j.$$

Notice that $q_{n-1}$ is intentionally absent: the full prefix of $a$ would correspond to an empty prefix of $p$, which the problem never asks about.

Set $x=k\oplus n.$ Our entire task is now to construct a permutation $a$ such that $q_0\oplus q_1\oplus\cdots\oplus q_{n-2}=x.$ We will then output $p$ as the reverse of $a$.

When is it possible?

Let $B$ be the smallest power of two satisfying $B\ge n$. Equivalently, $B$ is the smallest power of two strictly greater than $n-1$.

Every $q_j$ is one of the values $0,1,\ldots,n-1$, so $q_j<B$. Because $B$ is a power of two, every bit at position $\log_2 B$ or higher is zero in every $q_j$. Their XOR also has all those bits zero. Therefore, $x<B$ is necessary.

If $x\ge B$, the answer is NO. XOR is weird, but it cannot invent a bit that none of its operands has.

It remains to show that every $x<B$ is achievable.

Building the reversed permutation

We only need to control a tiny prefix of $a$. After placing $0$, all later prefix minima equal $0$, so the remaining unused values can be dumped afterward in any order.

Case 1: $x=0$

Start with $a=[0,\ldots].$ All relevant prefix minima are $0$, so their XOR is $0$.

Case 2: $1\le x<n$

Here $x$ itself is a legal permutation value. Start with $a=[x,0,\ldots].$ The relevant prefix minima are $x$ followed by zeroes, if any. Their XOR is exactly $x$.

Case 3: $n\le x<B$

The desired value is too large to place directly in the permutation. We split it into two legal prefix minima. Define $y=(n-1)\oplus x$ and start with $a=[n-1,y,0,\ldots].$

We need to verify that $y$ is a valid new value. This case can occur only when $n<B$. Let $H=B/2$. Since $B$ is the smallest power of two at least $n$, we have $H\le n-1<x<B.$ Thus both $n-1$ and $x$ have highest set bit $H$. XOR removes that common bit, giving $y<H\le n-1.$ Also $y\ne0$, because $x\ne n-1$. Therefore $1\le y<n-1,$ so $n-1$, $y$, and $0$ are distinct legal values.

The relevant prefix minima begin with $n-1,\ y,\ 0,\ 0,\ldots$ because $y<n-1$. Their XOR is $(n-1)\oplus y=(n-1)\oplus((n-1)\oplus x)=x.$ If the array is so short that the prefix containing $0$ is the excluded full prefix of $a$, that changes nothing: the two required nonzero minima are still included, and omitted zeroes contribute nothing anyway.

In every case, append all still-unused values from $0$ through $n-1$ after this special prefix. The result is a permutation, and those appended values cannot alter any prefix minimum after $0$ has appeared.

Finally, reverse $a$ to obtain $p$.

Correctness proof

Suppose the algorithm outputs NO. Then $x=k\oplus n\ge B$. For every permutation, each relevant prefix minimum of its reverse is below $B$, so their XOR is also below $B$. It cannot equal $x`; therefore no valid permutation exists.

Now suppose the algorithm outputs a permutation. Its special values are distinct in each of the three cases, and every other value is appended exactly once, so $a$ and its reverse $p$ are permutations.

The construction makes the XOR of $q_0,\ldots,q_{n-2}$ equal to $x$: it is $0$ in the first case, $x$ followed by zeroes in the second case, and $(n-1)\oplus y=x$ followed by zeroes in the third case. Using the suffix-minimum identity,

$$\bigoplus_{i=0}^{n-1}f(i) =n\oplus x =n\oplus(k\oplus n) =k.$$

Thus every printed permutation satisfies the requirement.

For $n=1$, $B=1$. The feasibility test accepts only $x=k\oplus1=0$, meaning $k=1$, and outputs $[0]$. So the annoying edge case falls out automatically instead of demanding special-case spaghetti.

Complexity

Constructing and printing the permutation takes $O(n)$ time and $O(n)$ memory per test case. The total time is $O(\sum n)$, which fits the given bound.