Sequências e Subsequências Binárias
Você tem uma sequencia binária $$s$$ (ou seja, formada apenas por zeros e uns).
Sua tarefa é dividir a sequência no menor número de subsequências $$alternantes$$, ou seja cada subsequência se parece com $$010101…$$ ou $$101010101…$$, ou seja, não pode haver zeros ou uns adjacentes. Além disso, todos os números devem estar em exatamente uma subsequência.
Lembre-se que uma subsequência de $$s$$ é uma sequência que pode ser extraída de $$s$$ removendo algum número, possivelmente zero, de elementos de $$s$$, sem trocar a ordem relativa entre os elementos que sobraram. Por exemplo, algumas subsequências de $$1011101$$ são $$0$$, $$1$$, $$11111$$, $$0111$$, etc. Porém, $$000$$, $$101010$$ e $$11100$$ não são.
Entrada:
A primeira linha de entrada contém um inteiro $$t$$, o número de casos de teste. $$t$$ casos seguem.
A primeira linha de cada caso de teste contém um inteiro $$n$$, o tamanho de $$s$$. Então segue a sequência $$s$$.
Saída
Para cada caso de teste, imprima duas linhas:
Na primeira linha, imprima um inteiro $$k$$, o total de subsequências necessárias.
Na segunda linha, imprima $$n$$ inteiros em qual subsequência o $$i$$-ésimo número de $$s$$ deve pertencer.
Se houver mais de uma resposta possível, imprima qualquer uma.
Restrições:
- $$1 \leq t \leq 2*10^4$$
- $$1 \leq n \leq 2*10^5$$
- Garante-se também que a soma dos $$n$$s em todos os casos de teste não ultrapassa $$2*10^5$$.
| Entrada | Saida |
| 4 4 0011 6 111111 5 10101 8 01010000 |
2 1 2 2 1 6 1 2 3 4 5 6 1 1 1 1 1 1 4 1 1 1 1 1 2 3 4 |
Para submeter sua solução, use esse link.