Submission #732045

#	Time	Username	Problem	Language	Result	Execution time	Memory
732045		lucri	Paint By Numbers (IOI16_paint)	C++17	100 / 100	481 ms	123136 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
bool pd[200010][110][2];
int k,n,aibb[200010],aibw[200010],checkpoints[110][200010];
bool b[200010],w[200010];
void adaugab(int poz,int val)
{
    for(;poz<=n;poz+=(poz&(-poz)))
        aibb[poz]+=val;
}
int sumab(int poz)
{
    int ans=0;
    for(;poz>0;poz-=(poz&(-poz)))
        ans+=aibb[poz];
    return ans;
}
void adaugaw(int poz,int val)
{
    for(;poz<=n;poz+=(poz&(-poz)))
        aibw[poz]+=val;
}
int sumaw(int poz)
{
    int ans=0;
    for(;poz>0;poz-=(poz&(-poz)))
        ans+=aibw[poz];
    return ans;
}
std::string solve_puzzle(std::string s, std::vector<int> c)
{
    std::string ans;
    k=c.size();
    n=s.size();
    int nrb=0,nrw=0;
    pd[0][0][0]=true;
    for(int i=1;i<=n;++i)
    {
        if(s[i-1]=='X')
        {
            nrb++;
            adaugab(i,1);
        }
        else if(s[i-1]=='_')
        {
            nrw++;
            adaugaw(i,1);
        }
        if(nrb==0)
            pd[i][0][0]=true;
        for(int j=1;j<=k;++j)
        {
            if(i>=c[j-1]&&nrw-sumaw(i-c[j-1])==0)
                pd[i][j][1]=pd[i-c[j-1]][j-1][0];
            if(s[i-1]!='X')
                pd[i][j][0]=(pd[i-1][j][0]|pd[i-1][j][1]);
        }
    }
    checkpoints[k][0]=1;
    checkpoints[k][1]=n;
    for(int j=k;j>=1;--j)
    {
        int poza=1;
        for(int i=checkpoints[j][1];i>=1;--i)
        {
            if(pd[i][j][0]==true)
                w[i]=true;
            if(pd[i][j][1]==true)
            {
                w[i-c[j-1]]=true;
                for(int q=0;q<c[j-1];++q)
                    b[i-q]=true;
                checkpoints[j-1][++checkpoints[j-1][0]]=i-c[j-1]-1;
                if(pd[i][j][0]==false)
                {
                    while(poza<=checkpoints[j][0]&&i<=checkpoints[j][poza])
                        ++poza;
                    i=checkpoints[j][poza]+1;
                }
            }
        }
    }
    for(int i=checkpoints[0][1];i>=1;--i)
        w[i]=true;
    for(int i=1;i<=n;++i)
        if(w[i]&&b[i])
            ans+='?';
        else if(w[i])
            ans+='_';
        else if(b[i])
            ans+='X';
    return ans;
}

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 21 / 21
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10