2020C.md (1474B)
1 Source: https://codeforces.com/problemset/problem/2020/C 2 3 C. Bitwise Balancing 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 You are given three non-negative integers $b$, $c$, and $d$. 22 23 Please find a non-negative integer $a \in [0, 2^{61}]$ such that $(a\, |\, b)-(a\, \&\, c)=d$, where $|$ and $\&$ denote the [bitwise OR operation](https://en.wikipedia.org/wiki/Bitwise_operation#OR) and the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND), respectively. 24 25 If such an $a$ exists, print its value. If there is no solution, print a single integer $-1$. If there are multiple solutions, print any of them. 26 27 Input 28 29 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). The description of the test cases follows. 30 31 The only line of each test case contains three positive integers $b$, $c$, and $d$ ($0 \le b, c, d \le 10^{18}$). 32 33 Output 34 35 For each test case, output the value of $a$, or $-1$ if there is no solution. Please note that $a$ must be non-negative and cannot exceed $2^{61}$. 36 37 Example 38 39 Input 40 41 ``` 42 3 43 44 2 2 2 45 46 4 2 6 47 48 10 2 14 49 ``` 50 51 Output 52 53 ``` 54 0 55 -1 56 12 57 ``` 58 59 Note 60 61 In the first test case, $(0\,|\,2)-(0\,\&\,2)=2-0=2$. So, $a = 0$ is a correct answer. 62 63 In the second test case, no value of $a$ satisfies the equation. 64 65 In the third test case, $(12\,|\,10)-(12\,\&\,2)=14-0=14$. So, $a = 12$ is a correct answer.