2094E.md (1338B)
1 Source: https://codeforces.com/problemset/problem/2094/E 2 3 E. Boneca Ambalabu 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Boneca Ambalabu gives you a sequence of $n$ integers $a_1,a_2,\ldots,a_n$. 22 23 Output the maximum value of $(a_k\oplus a_1)+(a_k\oplus a_2)+\ldots+(a_k\oplus a_n)$ among all $1 \leq k \leq n$. Note that $\oplus$ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). 24 25 Input 26 27 The first line contains an integer $t$ ($1 \leq t \leq 10^4$) – the number of independent test cases. 28 29 The first line of each test case contains an integer $n$ ($1 \leq n\leq 2\cdot 10^5$) – the length of the array. 30 31 The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0 \leq a_i \lt 2^{30}$). 32 33 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$. 34 35 Output 36 37 For each test case, output the maximum value on a new line. 38 39 Example 40 41 Input 42 43 ``` 44 5 45 46 3 47 48 18 18 18 49 50 5 51 52 1 2 4 8 16 53 54 5 55 56 8 13 4 5 15 57 58 6 59 60 625 676 729 784 841 900 61 62 1 63 64 1 65 ``` 66 67 Output 68 69 ``` 70 0 71 79 72 37 73 1555 74 0 75 ``` 76 77 Note 78 79 In the first test case, the best we can do is $(18\oplus18)+(18\oplus18)+(18\oplus18)=0$. 80 81 In the second test case, we choose $k=5$ to get $(16\oplus1)+(16\oplus2)+(16\oplus4)+(16\oplus8)+(16\oplus16)=79$.