Xor Permutations
Contest: Codeforces Round 562 (Div. 1)
Difficulty rating: 3100
Tags: constructive algorithms, math

Toad Mikhail has an array of $$$2^k$$$ integers $$$a_1, a_2, \ldots, a_{2^k}$$$.

Find two permutations $$$p$$$ and $$$q$$$ of integers $$$0, 1, \ldots, 2^k-1$$$, such that $$$a_i$$$ is equal to $$$p_i \oplus q_i$$$ for all possible $$$i$$$, or determine there are no such permutations. Here $$$\oplus$$$ denotes the bitwise XOR operation.

Input format:
The first line contains one integer $$$k$$$ ($$$2 \leq k \leq 12$$$), denoting that the size of the array is $$$2^k$$$.

The next line contains $$$2^k$$$ space-separated integers $$$a_1, a_2, \ldots, a_{2^k}$$$ ($$$0 \leq a_i < 2^k$$$) — the elements of the given array.

Output format:
If the given array can't be represented as element-wise XOR of two permutations of integers $$$0, 1, \ldots, 2^k-1$$$, print "Fou".

Otherwise, print "Shi" in the first line.

The next two lines should contain the description of two suitable permutations. The first of these lines should contain $$$2^k$$$ space-separated distinct integers $$$p_{1}, p_{2}, \ldots, p_{2^k}$$$, and the second line should contain $$$2^k$$$ space-separated distinct integers $$$q_{1}, q_{2}, \ldots, q_{2^k}$$$.

All elements of $$$p$$$ and $$$q$$$ should be between $$$0$$$ and $$$2^k - 1$$$, inclusive; $$$p_i \oplus q_i$$$ should be equal to $$$a_i$$$ for all $$$i$$$ such that $$$1 \leq i \leq 2^k$$$. If there are several possible solutions, you can print any.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
2
0 1 2 3

Example output:
Shi
2 0 1 3 
2 1 3 0

Example input:
2
0 0 0 0

Example output:
Shi
0 1 2 3 
0 1 2 3

Editorial:
If xor of all elements of the array is not zero, then the answer is "Fou".
Now let's assume that you have two permutations $$$p,q$$$ and when xored they are producing an array $$$a$$$.
I will show that it is possible to change any two elements $$$a_i, a_j$$$ to elements $$$a_i \oplus x, a_j \oplus x$$$ with some transformation of the given permutations.
Let's change $$$a_i, a_j$$$ to $$$a_i \oplus x, a_j \oplus x$$$.
Let's find such $$$t$$$, that $$$a_i \oplus q_i = p_t$$$.
If $$$t$$$ is equal to $$$i$$$ or $$$i+1$$$, then you can make some swaps to "fix" the array, to make it satisfy $$$a_i = p_i \oplus q_i$$$ for all $$$i$$$.
Now you have:
• $$$p_t, q_t, a_t$$$ at position $$$t$$$
• $$$p_i, q_i, a_i$$$ at position $$$i$$$
• $$$p_j, q_j, a_j$$$ at position $$$j$$$
Let's make some swaps at these positions to transform it to:
• $$$p_i, q_j, a_t$$$ at position $$$t$$$
• $$$p_t, q_i, a_i$$$ at position $$$i$$$
• $$$p_j, q_t, a_j$$$ at position $$$j$$$
Now, after you make these transition, you will have $$$p_i \oplus q_i = a_i$$$, and now you need to "fix" positions $$$t$$$ and $$$j$$$, and just process recursively.
Lemma: this thing will end in $$$O(n)$$$ operations.
______________________________________________________________________________________
Proof: Let's assume that at some two moments you have $$$p_t$$$ coincided with some $$$p_t$$$ earlier, let's check the first that moment.
For simplicity of the proof, let's assume that numbers are moving like that:
• $$$p_t, q_i, a_i$$$ at position $$$t$$$
• $$$p_i, q_j, a_t$$$ at position $$$i$$$
• $$$p_j, q_t, a_j$$$ at position $$$j$$$
(So $$$p_i$$$'s are constant, and $$$a_i$$$'s are changing now. Obviously, it is equivalent to the previous transformation)
Now, assume, that you had numbers:
• $$$p_t, q_t, a_t$$$ at position $$$t$$$
• $$$p_i, q_x, a_y$$$ at position $$$i$$$ (1)
• $$$p_j, q_y, a_j$$$ at position $$$j$$$ (2)
and then, you will make one transformation, and everything will go to:
• $$$p_t, q_x, a_y$$$ at position $$$t$$$
• $$$p_i, q_y, a_t$$$ at position $$$i$$$
• $$$p_j, q_t, a_j$$$ at position $$$j$$$
After that, before you will be stuck into described earlier equality:
• $$$p_t, q_x, a_y$$$ at position $$$t$$$
• $$$p_i, q_v, a_u$$$ at position $$$i$$$
• $$$p_j, q_u, a_j$$$ at position $$$j$$$
And after swapping with $$$t$$$
• $$$p_i, q_u, a_y$$$ at position $$$i$$$ (3)
• $$$p_j, q_x, a_j$$$ at position $$$j$$$ (4)
Let's look at (1), (2) and (3), (4)
From (1), (2), we can see $$$q_y = p_i \oplus q_x \oplus a_y \oplus p_j \oplus a_j$$$
From (3), (4), we can see $$$q_u = p_i \oplus a_y \oplus p_j \oplus q_x \oplus a_j$$$
So $$$q_y = q_u$$$, but $$$u \neq y$$$, so it is a contradiction, because $$$q$$$ is a permutation.. _________________________________________________________________________________
Ok, using these operations it is pretty simple to get an arbitrary array. Just start with $$$0,0,\ldots,0$$$ (two equal permutations). And then make $$$a_i = b_i, a_{i+1} = a_{i+1} \oplus (a_i \oplus b_i)$$$, at the end you will have one element rest and it will be good because initially xor was zero.
My solution.