noic-solucao-intermediario-s66.cpp

// Noic - Problemas da Semana 66 
// Nivel Intermédiario
// Solução por Samyra Almeida

#include <bits/stdc++.h>
 
using namespace std;
 
const int maxn = 3e5+10;
 
int n, k, pref[maxn], v[maxn];

int busca(int val) // faço a busca binária do tipo lower bound, ou seja, que ira retornar a posição da 1 aparição de val.
{
	int ini = 1, fim = n, pos = n+1;
	
	while(ini <= fim)
	{
		int mid = (ini + fim) >> 1;
 
		if(pref[mid] >= val)
		{
			pos = mid;
			fim = mid - 1;
		}
		else
		{
			ini = mid + 1;
		}
	}
 
	return pos;
}

int main()
{
 	scanf("%d %d", &n, &k);
 
	for(int i = 1 ; i <= n ; ++i)
	{
		cin >> v[i];

		pref[i] = pref[i - 1] + (!v[i]); // monto a soma de prefixos.
	}
 
	int ini = 0, fim = 0;
	
	for(int i = 1 ; i <= n ; ++i)
	{	 
		int x;
	
		if(v[i]) // se v[i] = 1.
		{
			x = busca(pref[i] + k + 1); // faço a busca da posição, como foi explicado acima.
		}
		else // se v[i] = 0.
		{
			if(k == 0) continue; // se não consigo mudar ninguem, ignoro esse caso.

			x = busca(pref[i] + k); // faço a busca da posição, como foi explicado acima.
		}
			

		if(x - i >= fim - ini + 1) // checo se o intervalo que eu achei é maior que a minha resposta atual, vale lembrar que:
		{						   // x - 1 é o final do intevalo, portanto fica x - 1 - i + 1 = x - i.
			ini = i;
			fim = x - 1;
		}
	}
	
	if(ini == 0 && fim == 0) printf("0\n"); // esse caso acontece se não existir nenhum 0 no vetor ou se k = 0
	
	else printf("%d\n", fim - ini + 1); // se não imprimo o tamanho do intervalo de uns.

	if(ini != fim || (ini == fim && k > 0 && ini != 0)) // se ini e fim são posições diferentes ou se ini = fim e eu consigo
	{													// mudar aquela posição e ini não é 0, mudo o intervalo para uns.
		for(int i = ini ; i <= fim ; ++i) 				 
			v[i] = 1;
	}
	
	for(int i = 1 ; i <= n ; ++i) printf("%d ", v[i]); // imprimo o vetor final.
	
	printf("\n");
}