제출 #732049

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
732049		lucri	Paint By Numbers (IOI16_paint)	C++17	90 / 100	59 ms	40644 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
bool pd[200010][110][2];
int k,n,aib[200010],checkpoints[110][200010];
bool b[200010],w[200010],aint[200010];
void adauga(int poz,int val)
{
    for(;poz<=n;poz+=(poz&(-poz)))
        aib[poz]+=val;
}
int suma(int poz)
{
    int ans=0;
    for(;poz>0;poz-=(poz&(-poz)))
        ans+=aib[poz];
    return ans;
}
void adaugab(int poz,int b,int e,int bi,int ei)
{
    if(aint[poz]==true||b>ei||e<bi)
        return;
    if(bi<=b&&e<=ei)
    {
        aint[poz]=true;
        return;
    }
    adaugab(poz*2,b,(b+e)/2,bi,ei);
    adaugab(poz*2+1,(b+e)/2+1,e,bi,ei);
}
bool black(int poz,int b,int e,int pozval)
{
    if(b>pozval||e<pozval)
        return 0;
    if(aint[poz]==true||b==e)
    {
        return aint[poz];
    }
    return (black(poz*2,b,(b+e)/2,pozval)|black(poz*2+1,(b+e)/2+1,e,pozval));
}
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++;
        else if(s[i-1]=='_')
        {
            nrw++;
            adauga(i,1);
        }
        if(nrb==0)
            pd[i][0][0]=true;
        for(int j=1;j<=k;++j)
        {
            if(i>=c[j-1]&&nrw-suma(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;
                adaugab(1,1,n,i-c[j-1]+1,i);
                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)
        b[i]=black(1,1,n,i);
    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: 0 / 10