subsequências.cpp

#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--;
	}
}