Popcount and XOR

AtCoder

IDabc347_d

Time2000ms

Memory256MB

Difficulty—

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 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 \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$ [samples]

Samples

Input #1

3 4 7

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.

Input #2

34 56 998244353

Output #2

\-1

No pair of non-negative integers satisfies the conditions.

Input #3

39 47 530423800524412070

Output #3

540431255696862041 10008854347644927

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

API Response (JSON)

{
  "problem": {
    "name": "Popcount and XOR",
    "description": {
      "content": "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 ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc347_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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 ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments