Swap if Equal Length and Sum

AtCoder

IDagc074_b

Time2000ms

Memory256MB

Difficulty—

You are given integer sequences $A=(A_1,A_2,\dots,A_N),\; B=(B_1,B_2,\dots,B_N)$ of length $N$ consisting of $0$ and $1$. Let $A[i,j]$ denote the contiguous subsequence from the $i$\-th through $j$\-th elements of sequence $A$. If $i>j$, $A[i,j]$ is a sequence of length $0$. You can perform the following operation on $A$ at most $\lfloor\frac{N}{2}\rfloor$ times: * Choose four integers $a,b,c,d$ that satisfy the following three conditions: * $1 \leq a \leq b < c \leq d \leq N$ * $b-a=d-c$ * $\sum_{i=a}^{b}{A_i}=\sum_{i=c}^{d}{A_i}$ * Swap $A[a,b]$ and $A[c,d]$. More precisely, replace $A$ with the concatenation of $A[1,a-1]$, $A[c,d]$, $A[b+1,c-1]$, $A[a,b]$, $A[d+1,N]$ in this order. Determine whether it is possible to make $A$ match $B$, and if possible, construct one sequence of operations. Solve $T$ test cases per input. ## Constraints * $1 \leq T \leq 25000$ * $2 \leq N \leq 2 \times 10^5$ * $0 \leq A_i \leq 1$ * $0 \leq B_i \leq 1$ * The sum of $N$ over all test cases is at most $2\times 10^5$. * All input values are integers. ## Input The input is given from Standard Input in the following format: $T$ $case_1$ $case_2$ $\vdots$ $case_T$ Each case is given in the following format: $N$ $A_1$ $A_2$ $\dots$ $A_N$ $B_1$ $B_2$ $\dots$ $B_N$ [samples]

Samples

Input #1

3
8
1 0 0 1 0 1 0 1
0 0 1 1 1 0 1 0
2
0 0
1 0
3
1 1 1
1 1 1

Output #1

Yes
2
3 4 6 7
1 4 5 8
No
Yes
0

In the first test case, $A$ is initially $(1,0,0,1,0,1,0,1)$.  
Performing the operation with $(a,b,c,d)=(3,4,6,7)$ changes $A$ to $(1,0,1,0,0,0,1,1)$.  
Then, performing the operation with $(a,b,c,d)=(1,4,5,8)$ changes $A$ to $(0,0,1,1,1,0,1,0)$, which matches $B$.  
In the second test case, it is impossible to make $A$ match $B$.  
In the third test case, $A$ already matches $B$ from the beginning.

API Response (JSON)

{
  "problem": {
    "name": "Swap if Equal Length and Sum",
    "description": {
      "content": "You are given integer sequences $A=(A_1,A_2,\\dots,A_N),\\; B=(B_1,B_2,\\dots,B_N)$ of length $N$ consisting of $0$ and $1$. Let $A[i,j]$ denote the contiguous subsequence from the $i$\\-th through $j$\\-t",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc074_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given integer sequences $A=(A_1,A_2,\\dots,A_N),\\; B=(B_1,B_2,\\dots,B_N)$ of length $N$ consisting of $0$ and $1$. Let $A[i,j]$ denote the contiguous subsequence from the $i$\\-th through $j$\\-t...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments