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 
-é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 , 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 como o novo contador, e colocando esse valor no vector de zeros. Podemos fazer o mesmo para caso o -ésimo item seja zero, porém com o vector de uns.
Segue o código, comentando, para melhor compreensão da solução:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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--; | |
| } | |
| } |