Informática – Nível Iniciante – Semana 20

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.