← 返回题目列表

AtCoder · arc193_d

D. 磁铁

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

分数: 1000 点

问题陈述

你有两个长度-N 字符串 A = A_1A_2 \ldots A_N 和 B = B_1B_2 \ldots B_N,每个由 0 和 1.

有 N 方块从左到右排成一行。对于 i = 1, 2, \ldots, N, i从左边算起第一个方格称为方格 i。最初,正方形 i 包含一个片段,如果 A_i = 1,并且如果 A_i = 0.

您可以重复以下操作任意次数(可能为零):

  • 选择一个整数 i 之间 1 和 N,包括在内。
  • 同时将所有棋子移近一格 i。也就是说,对于每一块,让平方 j 是其当前位置和方块 j' 为其新位置,并且以下内容成立:
    • if i < j,那么 j' = j-1;
    • if i > j,那么 j' = j+1;
    • if i = j,那么 j' = j.

确定是否有可能达到满足以下条件的配置,如果可能,则找到所需的最少操作数:

对于每个 i = 1, 2, \ldots, N,正方形中至少有一块 i 当且仅当 B_i = 1.

你被给予 T 独立测试用例。打印每个人的答案。

约束

  • 1 \leq T \leq 2 \times 10^5
  • 1 \leq N \leq 10^6
  • T 和 N 是整数。
  • A 和 B 是长度的字符串 N,每个由 0 和 1.
  • 存在 i 这样 A_i = 1.
  • 存在 i 这样 B_i = 1.
  • 总和 N 所有测试用例最多 10^6.

输入

输入由标准输入按以下格式给出:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

在这里, \mathrm{case}_i (i=1,2,\ldots,T) 表示 i- 第一个测试用例。

每个测试用例均按以下格式给出:

N
A
B

输出

打印 T 行。 对于每个 i = 1, 2, \ldots, T,在 i第行,打印 -1 如果不可能达到满足条件的配置 i- 第一个测试用例。否则,打印所需的最少操作数。


示例输入 1

3
8
01001101
00001011
3
010
111
20
10100011011110101011
00010001111101100000

示例输出 1

3
-1
5

输入具有三个独立的测试用例。

在第一个测试用例中,最初,方格中棋子的数量顺序为 (0, 1, 0, 0, 1, 1, 0, 1)。通过如下操作3次,即可满足条件:

  • 选择 i = 5。运行后配置为 (0, 0, 1, 0, 2, 0, 1, 0).
  • 选择 i = 8。运行后配置为 (0, 0, 0, 1, 0, 2, 0, 1).
  • 选择 i = 8。运行后配置为 (0, 0, 0, 0, 1, 0, 2, 1).

不可能用少于 3 次的操作来满足条件,所以答案是 3.

在第二个测试用例中,无论你如何执行操作,都无法满足条件,所以答案是 -1.