Solução por Pedro Racchetti
Conhecimentos utilizados:
- Entrada e saída
- Estruturas da STL: Vector e string
- Loops
Para esse problema, podemos manter dois vectors: um que contém todos os índices de subsequências que terminam em zero, e um que contém todas as subsequências que terminam em um, e um contador de quantas subsequências já foram utilizadas.
Assim, quando estivermos processando o $$i$$-ésimo item da sequência, suponha que seja um, basta verificarmos se existe alguma subsequência ja criada que termina em zero. Se houver, podemos escolher a ultima que foi colocada no vector de zeros, tirá-la do vector de zeros, marcá-la como a resposta para $$i$$, e coloca-lá no vector de uns, já que agora ela acaba em um. Se não houver nenhuma subsequência no vector de zeros, criamos uma nova subsequência, incrementando o contador, marcando a resposta de $$i$$ como o novo contador, e colocando esse valor no vector de zeros. Podemos fazer o mesmo para caso o $$i$$-ésimo item seja zero, porém com o vector de uns.
Segue o código, comentando, para melhor compreensão da solução:
https://gist.github.com/PedroRacchetti/5bc5e67f3d9d86f598354cc54826210b