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 ns 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.