AND-permutations
Contest: Codeforces Round 455 (Div. 2)
Difficulty rating: 2500
Tags: constructive algorithms

Given an integer N, find two permutations:

1. Permutation p of numbers from 1 to N such that pi ≠ i and pi & i = 0 for all i = 1, 2, ..., N.
2. Permutation q of numbers from 1 to N such that qi ≠ i and qi & i ≠ 0 for all i = 1, 2, ..., N.

& is the bitwise AND operation.

Input format:
The input consists of one line containing a single integer N (1 ≤ N ≤ 105).

Output format:
For each subtask, if the required permutation doesn't exist, output a single line containing the word "NO"; otherwise output the word "YES" in the first line and N elements of the permutation, separated by spaces, in the second line. If there are several possible permutations in a subtask, output any of them.

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

Example input:
3

Example output:
NO
NO

Example input:
6

Example output:
YES
6 5 4 3 2 1
YES
3 6 2 5 1 4

Editorial:
Permutation p (pi & i = 0)
If N is odd, the answer is NO. Indeed, any number in odd-numbered position i pi must be even, otherwise the last bit of pi&i is 1. For odd N there are less even numbers than odd-numbered positions, so at least one of the positions will hold an odd number, thus it's impossible to construct a required permutation.
If N is even, the required permutation exists. To build it, first observe that (2k - i)&(2k + i - 1) = 0. For example, for k = 5:
100000 = 25
011111 = 25 - 1
100001 = 25 + 1
011110 = 25 - 2
and so on.
We can use this fact to always match 2k - i and 2k + i - 1 with each other, that is, set p2k - i = 2k + i - 1 and p2k + i - 1 = 2k - i.
The full procedure for constructing the required permutation is as follows. For a given even N, find the maximum power of two that is less than or equal to N 2k. Match pairs of numbers 2k - i and 2k + i - 1 for each i = 1..N - 2k + 1. If we are not done yet, numbers from 1 to 2k - (N - 2k + 1) - 1 = 2k + 1 - N - 2 are still unmatched. Repeat the process for N' = 2k + 1 - N - 2.
For example, for N = 18 on the first step we set 2k = 16 and match numbers 15-16, 14-17 and 13-18. On the second step unmatched numbers are from 1 to 12, so we set 2k = 8 and match numbers 7-8, 6-9, 5-10, 4-11 and 3-12. On the third and the last step the remaining unmatched numbers are 1 and 2, so we set 2k = 2 and match numbers 1 and 2 with each other. After this no unmatched numbers are left, and we are done.
Permutation q (qi & i ≠ 0)
We can do a simple case analysis for N = 1..7 manually, noticing that the answer is NO for N = 1..5, a possible answer for N = 6 is 3 6 2 5 1 4 as given in problem statement, and a possible answer for N = 7 is 7 3 6 5 1 2 4.
If N is a power of two, then it is represented in binary as 10..0. We must have qN ≠ N, therefore qN < N, so the binary representation of qN is shorter than that of N. It follows that qN&N = 0, so the answer is NO in this case.
Finally, if N > 7 and N is not a power of two, the required permutation always exists, and can be built in the following way. Split all numbers from 1 to N into the following groups (k is the largest power of two which is still less than N):
1..7
8..15
16..31
...
2k - 1..2k - 1
2k..N
For the first group use the permutation that we found manually. For each of the remaining groups, use any permutation of numbers in this group (for example, a cyclic permutation). The numbers in each group have leading non-zero bit at the same position (which corresponds to the power of two at the beginning of the group), so it is guaranteed that qi&i contains a non-zero bit at least in that position.