Rezolvare PBinfo #2430

Oleg ține un istoric al vieții sale. O zi rea este notata cu 0, iar una bună este notată cu 1. Oleg numește un subșir zebră, un subșir care începe și se termină cu o zi rea și nu conține două zile de același fel pe poziții alăturate. De exemplu 0101, 001 și 0110 nu sunt subșiruri zebra, dar 010, 0 și 01010 sunt subșiruri zebră.

Cerința

Să se determine o împărțire a unui șir în subșiruri zebră.

Date de intrare

Programul citește de la tastatură un șir de caractere format din 0 și 1.

Date de ieșire

Programul va afișa pe ecran S, numărul de subșiruri, iar apoi, pe următoarele S linii numărul de zile componente ale fiecărui subșir și pozițiile din șirul inițial la care se află acestea. Dacă șirul nu se poate împărții în subșiruri zebră, atunci se va afișa -1.

Restricții și precizări

• Inputul conține cel mult 200.000 de caractere.
• Orice împărțire în subșiruri zebră este acceptată.

Exemplu 1:

Intrare

0010100

Ieșire

3
3 1 3 4
3 2 5 6
1 7

Exemplu 2:

Intrare

111

Ieșire

-1