Codeforces Round 658 (Div. 1) |
---|
Закончено |
Это сложная версия задачи. Различия между версиями заключаются в ограничениях на $$$n$$$ и необходимое количество операций. Вы можете делать взломы только если обе версии задачи сданы.
Есть две бинарные строки $$$a$$$ и $$$b$$$ длины $$$n$$$ (бинарная строка это строка, состоящая из символов $$$0$$$ и $$$1$$$). За одну операцию вы выбираете префикс строки $$$a$$$, меняете все биты этого префикса на другие ($$$0$$$ меняется на $$$1$$$, $$$1$$$ меняется на $$$0$$$) и переворачиваете этот префикс. За одну операцию вы выполняете оба этих действия.
Например, если $$$a=001011$$$ и вы выбираете префикс длины $$$3$$$, строка становится равной $$$011011$$$. Затем, если вы вы выберете всю строку как префикс для операции, она станет равной $$$001001$$$.
Ваша задача превратить строку $$$a$$$ в строку $$$b$$$ за не больше, чем $$$2n$$$ операций. Можно доказать, что это всегда возможно.
В первой строке находится единственное целое число $$$t$$$ ($$$1\le t\le 1000$$$) — количество наборов входных данных. Следующие $$$3t$$$ строк содержат описания наборов входных данных.
В первой строке каждого набора входных данных находится единственное целое число $$$n$$$ ($$$1\le n\le 10^5$$$) — длина бинарных строк.
Следующие две строки содержат две бинарные строки $$$a$$$ и $$$b$$$ длины $$$n$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.
Для каждого набора входных данных выведите целое число $$$k$$$ ($$$0\le k\le 2n$$$), затем $$$k$$$ целых чисел $$$p_1,\ldots,p_k$$$ ($$$1\le p_i\le n$$$). Здесь $$$k$$$ равно количеству операций, которое вы использовали и $$$p_i$$$ равно длине префикса в $$$i$$$-й операции.
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
В первом наборе входных данных процесс превращения выглядит так: $$$01\to 11\to 00\to 10$$$.
Во втором наборе входных данных процесс превращения выглядит так: $$$01011\to 00101\to 11101\to 01000\to 10100\to 00100\to 11100$$$.
В третьем наборе входных данных данные строки уже совпадают. Другим решением будет, например, сделать операцию с префиксом длины $$$2$$$, от чего строка $$$a$$$ не поменяется.
Название |
---|