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:
| #include<bits/stdc++.h> | |
| using namespace std; | |
| const int MAXN = 2e5 + 10; | |
| vector<int> uns, zeros; | |
| int resp[MAXN], n; | |
| string s; | |
| void reset(){ | |
| //aqui reinicializamos os vectors e lemos a entrada em cada casa de teste, | |
| //deixando o codigo mais claro. | |
| cin >> n; | |
| cin >> s; | |
| uns.clear(); | |
| zeros.clear(); | |
| } | |
| int main(){ | |
| int t; | |
| cin >> t; | |
| while(t > 0){ | |
| reset(); | |
| int contador = 0; | |
| for(int i = 0; i < n; i++){ | |
| if(s[i] == '0'){ | |
| //caso esse item seja 0, | |
| //verificamos se ele pode ser encaixado em alguma subsequencia ja criada que termina em 1 | |
| //se nao, criamos uma nova | |
| if(uns.empty()){ | |
| zeros.push_back(++contador); | |
| ans[i] = contador; | |
| } | |
| else{ | |
| int esse = uns[uns.size()-1]; | |
| ans[i] = esse; | |
| uns.pop_back(); | |
| zeros.push_back(esse); | |
| } | |
| }else{ | |
| //caso esse item seja 1, | |
| //verificamos se ele pode ser encaixado em alguma subsequencia ja criada que termina em 0 | |
| //se nao, criamos uma nova | |
| if(zeros.empty()){ | |
| uns.push_back(++contador); | |
| ans[i] = contador; | |
| }else{ | |
| int esse = zeros[zeros.size()-1]; | |
| ans[i] = esse; | |
| zeros.pop_back(); | |
| uns.push_back(esse); | |
| } | |
| } | |
| } | |
| //imprimimos a resposta. | |
| cout << totagr << endl; | |
| for(int i = 0; i < n; i++){ | |
| cout << ans[i] << " "; | |
| } | |
| cout << endl; | |
| t–; | |
| } | |
| } |
