103473: [Atcoder]ABC347 D - Popcount and XOR
Description
Score: $400$ points
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.
- $0 \leq X < 2^{60}$
- $0 \leq Y < 2^{60}$
- $\operatorname{popcount}(X) = a$
- $\operatorname{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 is1101, 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 \leq a \leq 60$
- $0 \leq b \leq 60$
- $0 \leq C < 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 $\operatorname{popcount}(X) = 3$. - $Y$ in binary is
11011, so $\operatorname{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.
Input
Output
得分：400分
问题描述
给定非负整数$a$，$b$和$C$。 确定是否存在一对非负整数$(X, Y)$满足以下五个条件。如果存在这样的对，请输出一个。
- $0 \leq X < 2^{60}$
- $0 \leq Y < 2^{60}$
- $\operatorname{popcount}(X) = a$
- $\operatorname{popcount}(Y) = b$
- $X \oplus Y = C$
其中，$\oplus$表示按位异或。
如果存在多个满足条件的对$(X, Y)$，您可以输出其中任意一个。
什么是popcount？
对于非负整数$x$，$x$的popcount是$x$的二进制表示中$1$的个数。 更准确地说，对于非负整数$x$，使得$\displaystyle x=\sum _ {i=0} ^ \infty b _ i2 ^ i\ (b _ i\in\lbrace0,1\rbrace)$，我们有$\displaystyle\operatorname{popcount}(x)=\sum _ {i=0} ^ \infty b _ i$。
例如，$13$的二进制表示是1101，因此$\operatorname{popcount}(13)=3$。
什么是按位异或？
对于非负整数$x, y$，按位异或$x \oplus y$定义如下。
- $x \oplus y$的二进制表示中第$2^k$位$\ (k\geq0)$为$1$，如果$x$和$y$的二进制表示中第$2^k$位$\ (k\geq0)$中恰好有一个为$1$，否则为$0$。
1001和0011，因此$9 \oplus 3 = 10$（二进制表示为1010）。
约束
- $0 \leq a \leq 60$
- $0 \leq b \leq 60$
- $0 \leq C < 2^{60}$
- 所有输入值均为整数。
输入
输入通过标准输入按以下格式给出：
$a$ $b$ $C$
输出
如果存在满足条件的非负整数对，选择这样的一个对$(X, Y)$，并按照顺序输出$X$和$Y$，中间用空格隔开。
如果没有这样的对，输出-1。
样例输入1
3 4 7
样例输出1
28 27
对$(X, Y) = (28, 27)$满足条件。
其中，$X$和$Y$的二进制表示分别是11100和11011。
- $X$的二进制表示是
11100，因此$\operatorname{popcount}(X) = 3$。 - $Y$的二进制表示是
11011，因此$\operatorname{popcount}(Y) = 4$。 - $X \oplus Y$的二进制表示是
00111，因此$X \oplus Y = 7$。
如果存在多个满足条件的非负整数对，您可以输出其中任意一个，因此输出42 45也是可以接受的。
样例输入2
34 56 998244353
样例输出2
-1
不存在满足条件的非负整数对。
样例输入3
39 47 530423800524412070
样例输出3
540431255696862041 10008854347644927
注意，要输出的值可能无法用$32$位整数表示。