309571: CF1700F. Puzzle
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Puzzle
题意翻译
给定两个 $2 \times n$ 的 $01$ 矩阵 $A$ 和 $B$，定义一次操作为交换 $A$ 中任意两个相邻的位置中的值，输出使得 $A=B$ 的最小操作次数，如果无法使 $A=B$ 则输出 $-1$。题目描述
Pupils Alice and Ibragim are best friends. It's Ibragim's birthday soon, so Alice decided to gift him a new puzzle. The puzzle can be represented as a matrix with $ 2 $ rows and $ n $ columns, every element of which is either $ 0 $ or $ 1 $ . In one move you can swap two values in neighboring cells. More formally, let's number rows $ 1 $ to $ 2 $ from top to bottom, and columns $ 1 $ to $ n $ from left to right. Also, let's denote a cell in row $ x $ and column $ y $ as $ (x, y) $ . We consider cells $ (x_1, y_1) $ and $ (x_2, y_2) $ neighboring if $ |x_1 - x_2| + |y_1 - y_2| = 1 $ . Alice doesn't like the way in which the cells are currently arranged, so she came up with her own arrangement, with which she wants to gift the puzzle to Ibragim. Since you are her smartest friend, she asked you to help her find the minimal possible number of operations in which she can get the desired arrangement. Find this number, or determine that it's not possible to get the new arrangement.输入输出格式
输入格式
The first line contains an integer $ n $ ( $ 1 \leq n \leq 200\,000 $ ) — the number of columns in the puzzle. Following two lines describe the current arrangement on the puzzle. Each line contains $ n $ integers, every one of which is either $ 0 $ or $ 1 $ . The last two lines describe Alice's desired arrangement in the same format.
输出格式
If it is possible to get the desired arrangement, print the minimal possible number of steps, otherwise print $ -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说明
In the first example the following sequence of swaps will suffice: - $ (2, 1), (1, 1) $ , - $ (1, 2), (1, 3) $ , - $ (2, 2), (2, 3) $ , - $ (1, 4), (1, 5) $ , - $ (2, 5), (2, 4) $ . It can be shown that $ 5 $ is the minimal possible answer in this case. In the second example no matter what swaps you do, you won't get the desired arrangement, so the answer is $ -1 $ .Input
题意翻译
给定两个 $2 \times n$ 的 $01$ 矩阵 $A$ 和 $B$，定义一次操作为交换 $A$ 中任意两个相邻的位置中的值，输出使得 $A=B$ 的最小操作次数，如果无法使 $A=B$ 则输出 $-1$。Output
题目大意：
给定两个2×n的01矩阵A和B，定义一次操作为交换A中任意两个相邻位置中的值，输出使得A=B的最小操作次数，如果无法使A=B则输出-1。
输入输出数据格式：
输入格式：
- 第一行包含一个整数n（1≤n≤200,000）——拼图中的列数。
- 接下来两行描述了拼图当前的排列。每行包含n个整数，每个数都是0或1。
- 最后两行以同样的格式描述了爱丽丝想要的排列。
输出格式：
- 如果可以得到想要的排列，打印出最小可能的步数，否则打印-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。题目大意： 给定两个2×n的01矩阵A和B，定义一次操作为交换A中任意两个相邻位置中的值，输出使得A=B的最小操作次数，如果无法使A=B则输出-1。 输入输出数据格式： 输入格式： - 第一行包含一个整数n（1≤n≤200,000）——拼图中的列数。 - 接下来两行描述了拼图当前的排列。每行包含n个整数，每个数都是0或1。 - 最后两行以同样的格式描述了爱丽丝想要的排列。 输出格式： - 如果可以得到想要的排列，打印出最小可能的步数，否则打印-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。
给定两个2×n的01矩阵A和B，定义一次操作为交换A中任意两个相邻位置中的值，输出使得A=B的最小操作次数，如果无法使A=B则输出-1。
输入输出数据格式：
输入格式：
- 第一行包含一个整数n（1≤n≤200,000）——拼图中的列数。
- 接下来两行描述了拼图当前的排列。每行包含n个整数，每个数都是0或1。
- 最后两行以同样的格式描述了爱丽丝想要的排列。
输出格式：
- 如果可以得到想要的排列，打印出最小可能的步数，否则打印-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。题目大意： 给定两个2×n的01矩阵A和B，定义一次操作为交换A中任意两个相邻位置中的值，输出使得A=B的最小操作次数，如果无法使A=B则输出-1。 输入输出数据格式： 输入格式： - 第一行包含一个整数n（1≤n≤200,000）——拼图中的列数。 - 接下来两行描述了拼图当前的排列。每行包含n个整数，每个数都是0或1。 - 最后两行以同样的格式描述了爱丽丝想要的排列。 输出格式： - 如果可以得到想要的排列，打印出最小可能的步数，否则打印-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。