/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
非負整数 a,b,C が与えられます。 次の 5 つの条件をすべて満たす非負整数の組 (X,Y) が存在するか判定し、存在するならひとつ出力してください。
- 0\leq X\lt2 ^ {60}
- 0\leq Y\lt2 ^ {60}
- \operatorname{popcount}(X)=a
- \operatorname{popcount}(Y)=b
- X\oplus Y=C
ただし、\oplus はビットごとの排他的論理和を表します。
条件を満たす (X,Y) が複数存在する場合、どれを出力しても構いません。
popcount とは？
非負整数 x について x の popcount とは、x を 2 進法で表記したときの 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 を 2 進法で表記すると1101 なので、 \operatorname{popcount}(13)=3 となります。
ビットごとの排他的論理和とは？
非負整数 x,y について x,y のビットごとの排他的論理和 x\oplus y は以下のように定義されます。
- x\oplus y を 2 進法で表記したときの 2 ^ k\ (k\geq0) の位は、x,y を 2 進法で表記したときの 2 ^ k\ (k\geq0) の位の数のうち一方のみが 1 であれば 1 、そうでなければ 0 となる。
例えば、9,3 を 2 進法で表記するとそれぞれ 1001, 0011 なので、9\oplus3=10 となります（10 を 2 進法で表記すると 1010 です）。
制約
- 0\leq a\leq60
- 0\leq b\leq60
- 0\leq C\lt2 ^ {60}
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
a b C
出力
条件を満たす非負整数の組が存在するならば、そのような (X,Y) をひとつ選び X,Y をこの順に空白を区切りとして出力せよ。
存在しないならば、-1 を出力せよ。
入力例 1
3 4 7
出力例 1
28 27
(X,Y)=(28,27) は条件を満たします。
X,Y を 2 進法で表記するとそれぞれ 11100 と 11011 になります。
- X を 2 進法で表記すると
11100になるので、\operatorname{popcount}(X)=3 です。 - Y を 2 進法で表記すると
11011になるので、\operatorname{popcount}(Y)=4 です。 - X\oplus Y を 2 進法で表記すると
00111となり、X\oplus Y=7 です。
条件を満たす非負整数の組が複数存在する場合どれを出力しても構わないため、例えば 42 45 と出力しても正解になります。
入力例 2
34 56 998244353
出力例 2
-1
条件を満たす非負整数の組は存在しません。
入力例 3
39 47 530423800524412070
出力例 3
540431255696862041 10008854347644927
出力すべき値が 32\operatorname{bit} 整数に収まらない場合があります。
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 1s 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.