Popcount and XOR

题目描述

你被给定非负整数 $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)$，你可以输出其中任意一对。

输入格式

输入由标准输入按照下述格式给出： $a$ $b$ $C$

输出格式

如果存在满足条件的一对非负整数，选择这样一对 $(X, Y)$ 并按顺序打印 $X$ 和 $Y$，中间用一个空格分隔。 如果不存在这样的对，打印 $-1$。

3 4 7

28 27

34 56 998244353

-1

39 47 530423800524412070

540431255696862041 10008854347644927

提示

$0 \leq a \leq 60$ $0 \leq b \leq 60$ 0 \leq C < 2^{60} 所有输入值均为整数。这一对 $(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$ 也会被接受。
不存在满足条件的非负整数对。
注意要输出的值可能无法容纳在 32 位整数中。

标签: AtCoder|abc347D

来源

AtCoder|abc347D