Increment or Xor

AtCoder

IDagc057_c

Time2000ms

Memory256MB

Difficulty—

You are given a positive integer $N$ and a sequence $A = (A_0, A_1, \ldots, A_{2^N-1})$ of $2^N$ terms, where each $A_i$ is an integer between $0$ and $2^N-1$ (inclusive) and $A_i\neq A_j$ holds if $i\neq j$. You can perform the following two kinds of operations on $A$: * Operation $+$: For every $i$, change $A_i$ to $(A_i + 1) \bmod 2^N$. * Operation $\oplus$: Choose an integer $x$ between $0$ and $2^N-1$. For every $i$, change $A_i$ to $A_i\oplus x$. Here, $\oplus$ denotes bitwise $\mathrm{XOR}$. What is bitwise $\mathrm{XOR}$?The bitwise $\mathrm{XOR}$ of non-negative integers $A$ and $B$, $A \oplus B$, is defined as follows: * When $A \oplus B$ is written in base two, the digit in the $2^k$'s place ($k \geq 0$) is $1$ if exactly one of $A$ and $B$ is $1$, and $0$ otherwise. For example, we have $3 \oplus 5 = 6$ (in base two: $011 \oplus 101 = 110$). Your objective is to make $A_i = i$ for every $i$. Determine whether it is achievable. It can be proved that, under the Constraints of this problem, one can achieve the objective with at most $10^6$ operations if it is achievable at all. Print such a sequence of operations. ## Constraints * $1\leq N\leq 18$ * $0\leq A_i \leq 2^N - 1$ * $A_i\neq A_j$, if $i\neq j$ ## Input Input is given from Standard Input in the following format: $N$ $A_0$ $A_1$ $\ldots$ $A_{2^N - 1}$ [samples]

Samples

Input #1

3
5 0 3 6 1 4 7 2

Output #1

Yes
4
-1 6 -1 1

The sequence of operations above changes the sequence $A$ as follows.

*   Initially: $A = (5,0,3,6,1,4,7,2)$
*   Operation $+$: $A = (6,1,4,7,2,5,0,3)$
*   Operation $\oplus$ ($x = 6$)：$A = (0,7,2,1,4,3,6,5)$
*   Operation $+$: $A = (1,0,3,2,5,4,7,6)$
*   Operation $\oplus$ ($x = 1$)：$A = (0,1,2,3,4,5,6,7)$

Input #2

3
2 5 4 3 6 1 0 7

Output #2

No

No sequence of operations achieves the objective.

Input #3

3
0 1 2 3 4 5 6 7

Output #3

Yes
0

Performing zero operations achieves the objective. Whether an empty line is printed or not does not affect the verdict.

API Response (JSON)

{
  "problem": {
    "name": "Increment or Xor",
    "description": {
      "content": "You are given a positive integer $N$ and a sequence $A = (A_0, A_1, \\ldots, A_{2^N-1})$ of $2^N$ terms, where each $A_i$ is an integer between $0$ and $2^N-1$ (inclusive) and $A_i\\neq A_j$ holds if $i",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc057_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a positive integer $N$ and a sequence $A = (A_0, A_1, \\ldots, A_{2^N-1})$ of $2^N$ terms, where each $A_i$ is an integer between $0$ and $2^N-1$ (inclusive) and $A_i\\neq A_j$ holds if $i...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments