Cod sursa(job #2477823)

Utilizator EricEric Vilcu Eric Data 21 octombrie 2019 10:21:31
Problema Submultimi Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <iostream>
#include <cstring>
using namespace std;
int que[200015];
bool qd[200015];
char a[200002];
int n,k,S,Q,B;
bool kp;
//(i/2)*(i+((i+1)/2)+1)/2+((i+1)/2)*(i+(i+1)/2)/2+(n+i+1)(n-i)/2
void stabilizeQ()
{
    int q=Q;
    for(int i=B;i<Q;++i)
    {
        int K=que[i];
        if(a[K]<2)
        {
            if(K==0)
            {
                ++S;
                if(qd[i]){a[0]=a[n-1];que[q]= 1 ;qd[q++]=qd[i];}
                else     {a[0]=a[ 1 ];que[q]=n-1;qd[q++]=qd[i];}
            }
            else if(K==n-1)
            {
                ++S;
                if(qd[i]){a[K]=a[K-1];que[q]= 0 ;qd[q++]=qd[i];}
                else     {a[K]=a[ 0 ];que[q]=K-1;qd[q++]=qd[i];}
            }
            else
            {
                ++S;
                if(qd[i]){a[K]=a[K-1];que[q]=K+1;qd[q++]=qd[i];}
                else     {a[K]=a[K+1];que[q]=K-1;qd[q++]=qd[i];}
            }
        }
    }
    --k;
    B=Q;
    Q=q;
}
int main()
{
    cin>>n>>k>>a;kp=k%2;
    for(int i=0;i<n;++i)
    {
        if(a[i]=='B')a[i]=1;
        else a[i]=0;
    }
    if(a[n-1]%2==a[0]||a[1]==a[0]){a[0]+=2;++S;};
    for(int i=1;i<n-1;++i)
    {
        if(a[i-1]%2==a[i]||a[i+1]==a[i]){a[i]+=2;++S;}
    }
    if(a[n-2]%2==a[n-1]||a[0]%2==a[n-1]){a[n-1]+=2;++S;};
    if(S==0)
    {
        for(int i=0;i<n;++i)cout<<(a[i]^kp?'B':'W');
        return 0;
    }
    if(a[0]<2&&(a[1]>=2||a[n-1]>=2)){que[Q]=0;qd[Q++]=(a[n-1]>=2);}
    for(int i=1;i<n-1;++i)
    {
        if(a[i]<2&&(a[i+1]>=2||a[i-1]>=2)){que[Q]=i;qd[Q++]=(a[i-1]>=2);}
    }
    if(a[n-1]<2&&(a[1]>=2||a[n-1]>=2)){que[Q]=n-1;qd[Q++]=(a[n-2]>=2);}
    while(S<n&&k>0)
    {
        stabilizeQ();
    }
    for(int i=0;i<n;++i)if(a[i]<2)cout<<(a[i]^kp?'B':'W');
                        else cout<<(a[i]-2?'B':'W');
}