← 返回题目列表

Codeforces · 1700/F

F. 谜题

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

学生爱丽丝和易卜拉欣是最好的朋友。马上就要到易卜拉欣的生日了,所以爱丽丝决定送给他一个新拼图。该谜题可以表示为一个具有 $$$2$$$ 行和 $$$n$$$ 列的矩阵,其中每个元素都是 $$$0$$$ 或 $$$1$$$。一步操作中,您可以交换相邻单元格中的两个值。

更正式地说,让我们从上到下对行 $$$1$$$ 到 $$$2$$$ 进行编号,从左到右对 $$$1$$$ 到 $$$n$$$ 列进行编号。另外,我们将 $$$x$$$ 行和 $$$y$$$ 列中的单元格表示为 $$$(x, y)$$$。如果 $$$|x_1 - x_2|,我们认为单元格 $$$(x_1, y_1)$$$ 和 $$$(x_2, y_2)$$$ 相邻+ |y_1 - y_2| = 1$$$。

Alice 不喜欢当前单元格的排列方式,因此她想出了自己的排列方式,她想将拼图赠送给 Ibragim。由于你是她最聪明的朋友,她要求你帮助她找到尽可能少的操作次数,以便她能够得到想要的安排。找到这个号码,或者确定不可能得到新的安排。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 200\,000$$$) — 拼图中的列数。

以下两行描述了拼图上当前的排列。每一行包含 $$$n$$$ 个整数,每个整数要么是 $$$0$$$ 要么是 $$$1$$$。

最后两行以相同的格式描述了 Alice 所需的排列。

输出

如果可以获得所需的排列,则打印尽可能少的步骤数,否则打印 $$$-1$$$。

示例

输入 #1

5
0 1 0 1 0
1 1 0 0 1
1 0 1 0 1
0 0 1 1 0

输出 #1

5

输入 #2

3
1 0 0
0 0 0
0 0 0
0 0 0

输出 #2

-1

注意

在第一个示例中,以下交换序列就足够了:

- $$$(2, 1), (1, 1)$$$,
- $$$(1, 2), (1, 3)$$$,
- $$$(2, 2), (2, 3)$$$,
- $$$(1, 4), (1, 5)$$$,
- $$$(2, 5), (2, 4)$$$.

可以证明,$$$5$$$ 是这种情况下的最小可能答案。

在第二个示例中,无论您进行什么交换,都不会得到所需的排列,因此答案是 $$$-1$$$。