Solução por Samyra Almeida
Para resolver esse problema é necessário conhecer duas técnicas de programação, a primeira chama-se soma de prefixos e a segunda busca binária.
Bem, iremos realizar uma soma de prefixos da seguinte forma, sendo a quantidade de zeros da posição até a -ésima posição:
- Se , fazemos: .
- Caso contrário, fazemos: .
Com isso, note que o vetor esta ordenado, pois dado qualquer posição de , podemos garantir que ou é igual ao , ou uma unidade maior.
Sabendo disso, agora vamos pensar em como utilizar a busca binária.
Então, dada uma posição qualquer, vamos mudar os primeiros zeros que estão de até .
Para isso, vamos analisar dois casos:
- Se , mudamos o cara , agora temos zeros para mudar, para isso note que basta usarmos a busca binária para procurar a ultima posição , no vetor , que possui valor igual a , ou seja, a posição do cara que possui zeros a mais de até ele do que .
- Se , como no caso anterior, basta procurarmos a ultima posição , no vetor , que possui valor igual a .
Chame de o valor da posição que queremos achar. Para o valor utilizaremos uma lower bound no valor , e depois descontamos 1 da posição encontrada.
Após isso, basta checar se o intervalo de até é o maior até agora, se sim, atualizo a resposta.
Depois de rodar esse algoritmo para todas as posições de , imprimimos a resposta e atualizamos o intervalo que foi mudado para uns, e printamos o vetor
Segue código solução para maior compreensão:
// 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"); | |
} |