Это сложная версия задачи. Различия между версиями заключаются в ограничениях на \(n\) и необходимое количество операций. Вы можете делать взломы только если обе версии задачи сданы.
Есть две бинарные строки \(a\) и \(b\) длины \(n\) (бинарная строка это строка, состоящая из символов \(0\) и \(1\)). За одну операцию вы выбираете префикс строки \(a\), меняете все биты этого префикса на другие (\(0\) меняется на \(1\), \(1\) меняется на \(0\)) и переворачиваете этот префикс. За одну операцию вы выполняете оба этих действия.
Например, если \(a=001011\) и вы выбираете префикс длины \(3\), строка становится равной \(011011\). Затем, если вы вы выберете всю строку как префикс для операции, она станет равной \(001001\).
Ваша задача превратить строку \(a\) в строку \(b\) за не больше, чем \(2n\) операций. Можно доказать, что это всегда возможно.
Выходные данные
Для каждого набора входных данных выведите целое число \(k\) (\(0\le k\le 2n\)), затем \(k\) целых чисел \(p_1,\ldots,p_k\) (\(1\le p_i\le n\)). Здесь \(k\) равно количеству операций, которое вы использовали и \(p_i\) равно длине префикса в \(i\)-й операции.
Примечание
В первом наборе входных данных процесс превращения выглядит так: \(01\to 11\to 00\to 10\).
Во втором наборе входных данных процесс превращения выглядит так: \(01011\to 00101\to 11101\to 01000\to 10100\to 00100\to 11100\).
В третьем наборе входных данных данные строки уже совпадают. Другим решением будет, например, сделать операцию с префиксом длины \(2\), от чего строка \(a\) не поменяется.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2
01
10
5
01011
11100
2
01
01
10
0110011011
1000110100
1
0
1
|
3 1 2 1
6 5 2 5 3 1 2
0
9 4 1 2 10 4 1 2 1 5
1 1
|