Задача №115132. Пазл
Участникам, использующим язык Python3 , рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3 .
Школьники Алиса и Ибрагим — лучшие друзья. У Ибрагима скоро день рождения, и по этому поводу Алиса решила подарить ему новый пазл. Пазл можно представить в виде матрицы из \(2\) строк и \(n\) столбцов, каждый элемент которой \(0\) или \(1\). За один ход можно поменять местами два элемента, стоящие в соседних клетках.
Более формально, будем считать, что строки матриц пронумерованы сверху вниз от \(1\) до \(2\), а столбцы — слева направо от \(1\) до \(n\). Обозначим клетку на пересечении строки \(x\) и столбца \(y\) за \((x, y)\). Будем считать две клетки \((x_1, y_1)\) и \((x_2, y_2)\) соседними, если \(|x_1 - x_2| + |y_1 - y_2| = 1\).
Алисе не нравится, какой рисунок образуют клетки пазла в данный момент. Она придумала свой рисунок, с которым и планирует подарить Ибрагиму новый пазл, но для этого нужно привести пазл в соответствующее состояние.
В конце учебного года у Алисы очень плотное расписание, и она не хочет тратить на эту задачу много времени. Помогите Алисе найти минимальное количество ходов, за которое она может получить свой рисунок, или скажите, что это невозможно.
В первой строке вводится одно целое число \(n\) (\(1 \leq n \leq 200\,000\)) — количество столбцов в пазле.
Следующие две строки описывают рисунок, образованный пазлом в данный момент. В каждой строке вводятся \(n\) целых чисел, каждое из которых равно \(0\) или \(1\).
Следующие две строки описывают желаемый рисунок Алисы в том же формате.
Если Алиса не ошиблась и её рисунок можно получить, найдите и выведите минимальное необходимое количество ходов, иначе выведите \(-1\).
В первом примере из условия подойдет следующая последовательность обменов:
\((2, 1), (1, 1)\)
\((1, 2), (1, 3)\)
\((2, 2), (2, 3)\)
\((1, 4), (1, 5)\)
\((2, 5), (2, 4)\)
Можно показать, что меньшим числом обменов обойтись нельзя, поэтому ответ равен \(5\).
Во втором примере из условия никакая последовательность ходов не приводит пазл к нужному виду.
Тесты к этой задаче состоят из 8 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп.
| Доп. ограничения | ||||
| Группа | Баллы | \(n\) | Необходимые группы | Комментарий |
| 0 | 0 | – | – | Тесты из условия. |
| 1 | 16 | \(n \le 7\) | 0 | |
| 2 | 11 | \(n \le 17\) | 0, 1 | |
| 3 | 14 | \(n \le 50\) | 0 – 2 | |
| 4 | 8 | \(n \le 300\) | 0 – 3 | |
| 5 | 16 | \(n \le 3000\) | 0 – 4 | |
| 6 | 16 | – | – | Вторая строка каждого пазла состоит из нулей. |
| 7 | 9 | – | 6 | Вторая строка второго пазла состоит из нулей. |
| 8 | 10 | – | 0 – 7 |
5 0 1 0 1 0 1 1 0 0 1 1 0 1 0 1 0 0 1 1 0
5
3 1 0 0 0 0 0 0 0 0 0 0 0
-1