← 返回题目列表

AtCoder · agc074_b

B. 如果长度和总和相等则交换

中文机器翻译题面 查看原题

分数: 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 从头开始。