分数: 800 点
问题陈述
给定整数序列 A=(A_1,A_2,\dots,A_N),\; B=(B_1,B_2,\dots,B_N) 长度 N 组成 0 和 1。 让 A[i,j] 表示来自的连续子序列 i-th 至 j序列的第一个元素 A。如果 i>j, A[i,j] 是一个长度序列 0。 您可以执行以下操作 A 最多 \lfloor\frac{N}{2}\rfloor 次:
- 选择四个整数 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,如果可能的话,构造一个操作序列。
解决 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 是所需的操作次数, (a_k,b_k,c_k,d_k) 是在 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
在第一个测试用例中, A 最初是 (1,0,0,1,0,1,0,1).
执行操作 (a,b,c,d)=(3,4,6,7) 变化 A to (1,0,1,0,0,0,1,1).
然后,执行操作 (a,b,c,d)=(1,4,5,8) 变化 A to (0,0,1,1,1,0,1,0),匹配 B.
在第二个测试用例中,不可能使 A 匹配 B.
在第三个测试用例中, A 已匹配 B 从头开始。