Submission #711352

#	Time	Username	Problem	Language	Result	Execution time	Memory
711352		bin9638	Paint By Numbers (IOI16_paint)	C++17	100 / 100	449 ms	332620 KiB

paint

#include <bits/stdc++.h>

#ifndef SKY
#include "paint.h"
#endif // SKY
#include <cstdlib>

using namespace std;

#define ll long long
#define pb push_back
#define N 200010
#define ii pair<int,int>
#define fs first
#define sc seoncd

int l[N][105][2],r[N][105][2],k,n,white[N],black[N],sum[N],cnt[N],c[N];

string solve_puzzle(string s,vector<int> vec)
{
    n=s.size();
    s=" "+s;
    k=vec.size();
    for(int i=1;i<=k;i++)
        c[i]=vec[i-1];
    for(int i=1;i<=n;i++)
        sum[i]=sum[i-1]+(s[i]!='_');
    l[0][0][1]=r[n+1][k+1][1]=1;
    for(int i=1;i<=n;i++)
    {
        //black
        if(s[i]!='_')
        {
            for(int j=1;j<=k;j++)
                if(i>=c[j]&&sum[i]-sum[i-c[j]]==c[j])
                    l[i][j][0]|=l[i-c[j]][j-1][1];
        }
        //while
        if(s[i]!='X')
        {
            for(int j=0;j<=k;j++)
                l[i][j][1]|=(l[i-1][j][1]|l[i-1][j][0]);
        }
    }

    for(int i=n;i>=1;i--)
    {
        //black
        if(s[i]!='_')
        {
            for(int j=1;j<=k;j++)
                if(n-i+1>=c[j]&&sum[i+c[j]-1]-sum[i-1]==c[j])
                    r[i][j][0]|=r[i+c[j]][j+1][1];
        }
        if(s[i]!='X')
        {
            for(int j=1;j<=k+1;j++)
                r[i][j][1]|=(r[i+1][j][0]|r[i+1][j][1]);
        }
    }
    for(int i=1;i<=n;i++)
        if(s[i]!='X')
        {
            for(int j=0;j<=k;j++)
                if((l[i-1][j][0]|l[i-1][j][1])&&(r[i+1][j+1][0]|r[i+1][j+1][1]))
                {
                    white[i]=1;
                    break;
                }
        }
    for(int i=1;i<=n;i++)
        if(s[i]!='_')
        {
            for(int j=1;j<=k;j++)
                if(i>=c[j]&&sum[i]-sum[i-c[j]]==c[j]&&l[i-c[j]][j-1][1]&&r[i+1][j+1][1])
                {
                    black[i-c[j]+1]++;
                    black[i+1]--;
                }
        }
    for(int i=1;i<=n;i++)
        black[i]+=black[i-1];
    for(int i=1;i<=n;i++)
        black[i]=(black[i]>0);
    string kq="";
    for(int i=1;i<=n;i++)
    {
        if(black[i]==1&&white[i]==1)
        {
            kq.pb('?');
            continue;
        }
        if(black[i])
            kq.pb('X');
                else kq.pb('_');

    }
    return kq;
}

#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    string s;
    cin>>s;
    int k;
    vector<int>c;
    cin>>k;
    for(int i=1;i<=k;i++)
    {
        int u;
        cin>>u;
        c.pb(u);
    }
    cout<<solve_puzzle(s,c);
}
#endif

• 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