/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 800 点
問題文
0 と 1 からなる長さ N の整数列 A=(A_1,A_2,\dots,A_N),\; B=(B_1,B_2,\dots,B_N) が与えられます。 数列 A の i 番目から j 番目の連続部分列を A[i,j] と表すことにします。ただし、i>j のとき、A[i,j] は長さ 0 の数列とします。 A に対して、以下の操作を \lfloor\frac{N}{2}\rfloor 回まで行えます。
- 以下の 3 条件を満たす 4 整数 a,b,c,d を選ぶ。
- 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}
- A[a,b] と A[c,d] を入れ替える。より厳密には、A を、A[1,a-1], A[c,d], A[b+1,c-1], A[a,b], A[d+1,N] の順に結合した数列に置き換える。
A を B に一致させることが可能かどうかを判定して、可能ならばその操作手順を 1 つ構成してください。
1 つの入力につき、T 個のテストケースを解いてください。
制約
- 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
- 全てのテストケースにおける N の総和は 2\times 10^5 以下
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
T case_1 case_2 \vdots case_T
各ケースは以下の形式で与えられる。
N A_1 A_2 \dots A_N B_1 B_2 \dots B_N
出力
答えを以下の形式で出力せよ。
output_1 output_2 \vdots output_T
ここで、output_t は t 番目のテストケースへの出力を表す。
各ケースでは、A を B に一致させられるならば、必要な操作回数を K 回、k 回目の操作で選ぶ (a,b,c,d) を (a_k,b_k,c_k,d_k) として、以下の形式で出力せよ。
Yes K a_1 b_1 c_1 d_1 a_2 b_2 c_2 d_2 \vdots a_K b_K c_K d_K
A を B に一致させることが不可能ならば No を出力せよ。
入力例 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
出力例 1
Yes 2 3 4 6 7 1 4 5 8 No Yes 0
1 つ目のテストケースでは、A は最初、(1,0,0,1,0,1,0,1) です。
(a,b,c,d)=(3,4,6,7) を選んで操作を行うと、A は (1,0,1,0,0,0,1,1) になります。
次に、(a,b,c,d)=(1,4,5,8) を選んで操作を行うと、A は (0,0,1,1,1,0,1,0) になり、B に一致します。
2 つ目のテストケースでは、A を B に一致させることはできません。
3 つ目のテストケースでは、A は最初から B に一致しています。
Score : 800 points
Problem Statement
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
Output
Output the answer in the following format:
output_1 output_2 \vdots output_T
Here, output_t represents the output for the t-th test case.
For each case, if you can make A match B, let K be the number of operations required and (a_k,b_k,c_k,d_k) be the values chosen in the k-th operation, then output in the following format:
Yes K a_1 b_1 c_1 d_1 a_2 b_2 c_2 d_2 \vdots a_K b_K c_K d_K
If it is impossible to make A match B, output No.
Sample 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
Sample 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.