1567B.md (1876B)
1 Source: https://codeforces.com/problemset/problem/1567/B 2 3 B. MEXor Mixup 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 Alice gave Bob two integers $a$ and $b$ ($a \gt 0$ and $b \ge 0$). Being a curious boy, Bob wrote down an array of non-negative integers with $\operatorname{MEX}$ value of all elements equal to $a$ and $\operatorname{XOR}$ value of all elements equal to $b$. 22 23 What is the shortest possible length of the array Bob wrote? 24 25 Recall that the $\operatorname{MEX}$ ([Minimum EXcluded](https://en.wikipedia.org/wiki/Mex_(mathematics))) of an array is the minimum non-negative integer that does not belong to the array and the $\operatorname{XOR}$ of an array is the [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) of all the elements of the array. 26 27 Input 28 29 The input consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 5 \cdot 10^4$) — the number of test cases. The description of the test cases follows. 30 31 The only line of each test case contains two integers $a$ and $b$ ($1 \leq a \leq 3 \cdot 10^5$; $0 \leq b \leq 3 \cdot 10^5$) — the $\operatorname{MEX}$ and $\operatorname{XOR}$ of the array, respectively. 32 33 Output 34 35 For each test case, output one (positive) integer — the length of the shortest array with $\operatorname{MEX}$ $a$ and $\operatorname{XOR}$ $b$. We can show that such an array always exists. 36 37 Example 38 39 Input 40 41 ``` 42 5 43 1 1 44 2 1 45 2 0 46 1 10000 47 2 10000 48 ``` 49 50 Output 51 52 ``` 53 3 54 2 55 3 56 2 57 3 58 ``` 59 60 Note 61 62 In the first test case, one of the shortest arrays with $\operatorname{MEX}$ $1$ and $\operatorname{XOR}$ $1$ is $[0, 2020, 2021]$. 63 64 In the second test case, one of the shortest arrays with $\operatorname{MEX}$ $2$ and $\operatorname{XOR}$ $1$ is $[0, 1]$. 65 66 It can be shown that these arrays are the shortest arrays possible.