Задача №113903. Зебры
Олег ведёт историю прожитых им дней, отмечая в ней каждый день либо как хороший, либо как плохой. Олег называет зеброй непустую последовательность дней, начинающуюся и заканчивающуюся плохим днём, в которой хорошие и плохие дни чередуются. Будем обозначать плохие дни за 0 , а хорошие за 1 . Тогда, например, последовательности дней 0 , 010 , 01010 являются зебрами, а последовательности 1 , 0110 и 0101 не являются.
Олег сообщил вам историю прожитых им дней в хронологическом порядке в виде строки из символов 0 и 1 , и теперь вас интересует, можно ли разбить историю Олега на несколько подпоследовательностей , каждая из которых является зеброй, и, если да, то как это можно сделать. Каждый день должен попасть ровно в одну подпоследовательность. Дни в каждой подпоследовательности должны следовать в хронологическом порядке. Обратите внимание, что подпоследовательность не обязана образовывать группу подряд идущих дней.
В единственной строке входных данных записана непустая строка s , состоящая из символов 0 и 1 , которая описывает историю дней, прожитых Олегом. Длина строки (обозначаемая дальше как | s | ) не превосходит 200 000 символов.
Если существует способ разбить историю дней на подпоследовательности, являющиеся зебрами, то в первой строке выведите число k ( 1 ≤ k ≤ | s | ) — получившееся количество подпоследовательностей. В i -й из k последующих строк выведите сперва целое число l i ( 1 ≤ l i ≤ | s | ) — длину i -й подпоследовательности, а затем l i индексов, обозначающих номера дней в истории, составляющих подпоследовательность. Номера должны следовать в порядке возрастания, нумерация начинается с единицы. Каждый номер от 1 до n должен попасть ровно в одну подпоследовательность. Если разбиения на подпоследовательности-зебры не существует, то выведите -1 .
Подпоследовательности можно выводить в любом порядке. Если возможных разбиений на подпоследовательности-зебры несколько, то разрешается вывести любое из них. Минимизировать или максимизировать величину k не требуется.
Тесты к этой задаче состоят из трёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.
0010100
3 1 1 5 2 3 4 5 6 1 7
111
-1