codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.