Submission #782184

#	Time	Username	Problem	Language	Result	Execution time	Memory
782184		BT21tata	Paint By Numbers (IOI16_paint)	C++17	100 / 100	241 ms	84872 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
#include <cstdlib>
using namespace std;

bool dp1[200005][205], dp2[200005][205];
int n, prx[200005], k, pre[200005], canx[200005], cane[200005];
string ans;

string solve_puzzle(string s, vector<int> c)
{
    n=s.length();
    k=c.size();
    s='0'+s;
    c.insert(c.begin(), 0);
    for(int i=1; i<=n; i++)
    {
        if(s[i]=='X') prx[i]=1;
        if(s[i]=='_') pre[i]=1;
        prx[i]+=prx[i-1];
        pre[i]+=pre[i-1];
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=k; j++)
        {
            // [i-c[j]+1   ...   i]
            if(i-c[j]<0) continue;
            if(j==1)
            {
                if(s[i]!='X') dp1[i][j]=dp1[i-1][j];
                if(pre[i]-pre[i-c[j]]==0 and prx[i-c[j]]==0) dp1[i][j]=1;
            }
            else
            {
                if(s[i]!='X') dp1[i][j]=dp1[i-1][j];
                if(pre[i]-pre[i-c[j]]==0 and dp1[i-c[j]-1][j-1] and s[i-c[j]]!='X') dp1[i][j]=1;
            }
        }
    }

    for(int i=n; i>=1; i--)
    {
        for(int j=k; j>=1; j--)
        {
            // [i  ...  i+c[j]-1]
            if(i+c[j]-1>n) continue;
            if(j==k)
            {
                if(s[i]!='X') dp2[i][j]=dp2[i+1][j];
                if(pre[i+c[j]-1]-pre[i-1]==0 and prx[n]-prx[i+c[j]-1]==0) dp2[i][j]=1;
            }
            else
            {
                if(s[i]!='X') dp2[i][j]=dp2[i+1][j];
                if(pre[i+c[j]-1]-pre[i-1]==0 and dp2[i+c[j]+1][j+1] and s[i+c[j]]!='X') dp2[i][j]=1;
            }
        }
    }

    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=k; j++)
        {
            // cout<<i<<' '<<j<<' '<<dp1[i][j]<<' '<<dp2[i][j]<<endl;
            if(s[i]!='X' and dp1[i-1][j] and ((prx[n]-prx[i]==0 and j==k) or dp2[i+1][j+1])) cane[i]=max(cane[i], 1);
            if(s[i]!='X' and (dp1[i-1][j-1] or (j==1 and prx[i-1]==0)) and dp2[i+1][j]) cane[i]=max(cane[i], 1);
            if(i+c[j]-1<=n)
            {
                // [i ... i+c[j]-1]
                if(s[i-1]!='X' and s[i+c[j]]!='X' and pre[i+c[j]-1]-pre[i-1]==0
                 and ((j==1 and prx[i-2]==0) or dp1[i-2][j-1]) and ((j==k and prx[n]-prx[min(n, i+c[j])]==0) or dp2[i+c[j]+1][j+1]))
                    canx[i]++, canx[i+c[j]]--;
            }
        }
    }
    for(int i=1; i<=n; i++)
        canx[i]+=canx[i-1];
    for(int i=1; i<=n; i++)
    {
        // cout<<"in cans : "<<i<<' '<<cane[i]<<' '<<canx[i]<<endl;
        if(s[i]=='.')
        {
            if(cane[i] and canx[i]) ans+='?';
            else if(canx[i]) ans+='X';
            else ans+='_';
        }
        else ans+=s[i];
    }
    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