407473: GYM102801 A Micro Structure Thread

Given a sequence $$$a$$$ consists $$$n$$$ distinct integers. Please construct a permutation $$$p$$$ and a sequence $$$b$$$ satisfied:

- Both $$$p$$$ and $$$b$$$ have exactly $$$n$$$ elements;

- For every $$$i \in [2,n]$$$ ,there exist an indice $$$j(1 \leq j \leq i-1)$$$ such that $$$b_i \oplus p_j=0$$$.

You need to minimize $$$\sum\limits_{i=2}^n popcount(a[p[i]] \oplus a[b[i]])$$$, where $$$popcount(x)$$$ represents the number of $$$1$$$ in the binary representation of $$$x$$$, $$$\oplus$$$ means bitwise exclusive OR operation.

The input consists of multiple test cases.

The first line contains an integer $$$T$$$ $$$(1 \leq T \leq 10)$$$ — the number of test cases. The description of the test cases follows.

The first line contains one integers $$$n$$$ $$$(1 \leq n \leq 2*10^5)$$$ .

The second line contains $$$n$$$ distinct integers $$$a_1,a_2,\dots,a_n(0 \leq a_i < 2^{18})$$$ .

For each test case, print three lines.

The first line contains one number, represents the minimum value.

The second line contains $$$n$$$ numbers $$$p_1,p_2,\dots,p_n$$$ — the permutation you construct.

The last line contains $$$n$$$ numbers $$$b_1,b_2,\dots,b_n$$$ — the sequence you construct.

If there are several answers, you can print any.

2
3
2 3 4
4
65 23 11 43

3
1 2 3 
3 1 1 
7
1 3 4 2 
4 1 3 3