AtCoder Beginner Contest 347 （ABCDEF题）视频讲解-D - Popcount and XOR

Problem Statement

You are given non-negative integers $a$, $b$, and $C$.
Determine if there is a pair of non-negative integers $(X,Y)$ that satisfies all of the following five conditions. If such a pair exists, print one.
KaTeX parse error: Expected 'EOF', got '&' at position 10: 0 \leq X &̲lt; 2^{60}
KaTeX parse error: Expected 'EOF', got '&' at position 10: 0 \leq Y &̲lt; 2^{60}
$\mathrm{popcount}(X)=a$
$\mathrm{popcount}(Y)=b$
$X\oplus Y=C$
Here, $\oplus$ denotes the bitwise XOR.
If multiple pairs $(X,Y)$ satisfy the conditions, you may print any of them.

What is popcount? For a non-negative integer $x$, the popcount of $x$ is the number of $1$s in the binary representation of $x$. More precisely, for a non-negative integer $x$ such that $\displaystyle x=\sum _ {i=0} ^ \infty b _ i2 ^ i\ (b _ i\in\lbrace0,1\rbrace)$, we have $\displaystyle\operatorname{popcount}(x)=\sum _ {i=0} ^ \infty b _ i$. For example, $13$ in binary is 1101, so $\operatorname{popcount}(13)=3$. What is bitwise XOR? For non-negative integers $x, y$, the bitwise exclusive OR $x \oplus y$ is defined as follows. The $2^k$'s place $\ (k\geq0)$ in the binary representation of $x \oplus y$ is $1$ if exactly one of the $2^k$'s places $\ (k\geq0)$ in the binary representations of $x$ and $y$ is $1$, and $0$ otherwise. For example, $9$ and $3$ in binary are 1001 and 0011, respectively, so $9 \oplus 3 = 10$ (in binary, 1010). #### Constraints

$0\le a\le 60$
$0\le b\le 60$
KaTeX parse error: Expected 'EOF', got '&' at position 10: 0 \leq C &̲lt; 2^{60}
All input values are integers.

Input

The input is given from Standard Input in the following format:

$a$ $b$ $C$

Output

If there is a pair of non-negative integers that satisfies the conditions, choose one such pair $(X,Y)$ and print $X$ and $Y$ in this order, with a space in between.
If no such pair exists, print -1.

Sample Input 1

3 4 7

Sample Output 1

28 27

The pair $(X,Y)=(28,27)$ satisfies the conditions.
Here, $X$ and $Y$ in binary are 11100 and 11011, respectively.
$X$ in binary is 11100, so $\mathrm{popcount}(X)=3$.
$Y$ in binary is 11011, so $\mathrm{popcount}(Y)=4$.
$X\oplus Y$ in binary is 00111, so $X\oplus Y=7$.
If multiple pairs of non-negative integers satisfy the conditions, you may print any of them, so printing 42 45, for example, would also be accepted.

Sample Input 2

34 56 998244353

Sample Output 2

-1

No pair of non-negative integers satisfies the conditions.

Sample Input 3

39 47 530423800524412070

Sample Output 3

540431255696862041 10008854347644927

Note that the values to be printed may not fit in $32$-bit integers.

Solution

具体见文末视频。

---

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int a, b, c;

	cin >> a >> b >> c;

	int r1 = 0, r2 = 0;
	for (int i = 0; i < 61; i ++)
		if (c >> i & 1) {
			if (a > b) r1 += (1ll << i), a --;
			else r2 += (1ll << i), b --;
		}
	if (a != b || a < 0 || b < 0) {
		cout << -1 << endl;
		return 0;
	}
	for (int i = 0; i < 61; i ++)
		if (!(c >> i & 1) && a && b)
			r1 += (1ll << i), r2 += (1ll << i), a --, b --;

	if (a || b) {
		cout << -1 << endl;
		return 0;
	}
	cout << r1 << " " << r2 << endl;

	return 0;
}

---