Unusual Sorting

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
You are given a sequence of distinct nonnegative integers $A_1, A_2, \dots, A_N$. For every nonnegative integer $x \lt 2^K$, let's define a function $f(x)$ as the number of inversions in the sequence $A_1 \oplus x, A_2 \oplus x, \dots, A_N \oplus x$. (An inversion in a sequence $X_1, X_2, \dots, X_N$ is a pair of indices $(i, j)$ such that $i \lt j$ and $X_i \gt X_j$.) Consider the sorted sequence of pairs $(f(x), x)$ for all integers $x \in [0, 2^K  1]$; a pair $(f(x_1), x_1)$ is earlier than $(f(x_2), x_2)$ in this sequence if $f(x_1) \lt f(x_2)$, or if $f(x_1) = f(x_2)$ and $x_1 \lt x_2$. You should find the second element (i.e. the number $x$) of the $P$th pair in this sequence. The sequence is indexed from 1. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains three spaceseparated integers $N$, $K$ and $P$.  The second line contains $N$ spaceseparated integers $A_1, A_2, \dots, A_N$. ### Output For each test case, print a single line containing one integer — the number $x$ generating the $P$th pair in the sorted sequence. ### Constraints  $1 \le T \le 20$  $1 \le N \le 10^6$  $1 \le K \le 30$  $1 \le P \le 2^K$  $0 \le A_i \lt 2^K$ for each valid $i$  the elements of $A$ are pairwise distinct  the sum of $N$ for all test cases does not exceed $10^6$ ### Subtasks **Subtask #1 (10 points):**  $1 \le T \le 10$  $1 \le K \le 10$  $1 \le N \le 100$ **Subtask #2 (20 points):**  $1 \le T \le 10$  $1 \le K \le 18$  the sum of $N$ for all test cases does not exceed $10^5$ **Subtask #3 (20 points):**  $1 \le T \le 5$  $1 \le K \le 30$  the sum of $N$ for all test cases does not exceed $10^5$ **Subtask #4 (50 points):** original constraints ### Example Input ``` 2 4 3 5 2 0 3 7 2 2 1 2 0 ``` ### Example Output ``` 4 2 ``` ### Explanation **Example case 1:** The values of $f(x)$ for all $0 \le x \le 7$ are as follows:  $x = 0$: $f(0) =$ number of inversions in $[2, 0, 3, 7] = 1$  $x = 1$: $f(1) =$ number of inversions in $[3, 1, 2, 6] = 2$  $x = 2$: $f(2) =$ number of inversions in $[0, 2, 1, 5] = 1$  $x = 3$: $f(3) =$ number of inversions in $[1, 3, 0, 4] = 2$  $x = 4$: $f(4) =$ number of inversions in $[6, 4, 7, 3] = 4$  $x = 5$: $f(5) =$ number of inversions in $[7, 5, 6, 2] = 5$  $x = 6$: $f(6) =$ number of inversions in $[4, 6, 5, 1] = 4$  $x = 7$: $f(7) =$ number of inversions in $[5, 7, 4, 0] = 5$ The sorted sequence of pairs $(f(x), x)$ is $[(1, 0), (1, 2), (2, 1), (2, 3), (4, 4), (4, 6), (5, 5), (5, 7)]$. We should find the $P=5$th pair, which is $(4, 4)$, so the answer is $4$.Author:  isaf27 
Editorial  https://discuss.codechef.com/problems/XORSORT2 
Tags  binarysearch, bitwiseoperatn, isaf27, isaf27, likecs, ltime61, mediumhard, meetinmiddle 
Date Added:  23062018 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 