Submission #73133

#	Time	Username	Problem	Language	Result	Execution time	Memory
73133		XmtosX	Paint By Numbers (IOI16_paint)	C++17	100 / 100	1628 ms	510408 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
const int N=4e5+5;

int n,k;
short memo[N][502];
bool can[N][502];
string s1;
vector <int> v;
bool dp (int pos,int cur)
{
    if (pos>=n)
        return (cur==k);
    short &ret= (memo[pos][cur]);
    if (ret!=-1)
        return (ret!=0);
    ret=0;
    if (s1[pos]=='_'||s1[pos]=='.')
        ret= dp(pos+1,cur);
    if (cur!=k&&can[pos][cur])
    {
        if (s1[pos]=='X'||s1[pos]=='.')
            ret+= (dp(pos+v[cur]+1,cur+1))*2;
    }
    return (ret!=0);
}
string solve_puzzle( string s,  vector<int> c)
{
    n=s.size();
    k=c.size();
    s1=s;
    memset(memo,-1,sizeof memo);
    v=c;
    for (int i=k-1;i>=0;i--)
    {
        int cnt=0;
        for (int j=n-1;j>=0;j--)
        {
            cnt+= (s[j]=='_');
            if (j+v[i]<n)
                cnt-= (s[j+v[i]]=='_');
            if (j+v[i]<=n)
                can[j][i]= (cnt==0);
            if (j+v[i]<n&&s[j+v[i]]=='X')
                can[j][i]=0;
        }
    }
    dp(0,0);
    string ans;
    int pfx[N];
    memset(pfx,0,sizeof pfx);
    for (int i=0;i<n;i++)
        for (int j=0;j<=k;j++)
            if (memo[i][j]==-1)
                memo[i][j]=0;
    for (int i=n-1;i>=0;i--)
    {
        for (int j=0;j<k;j++)
        {
            if (memo[i][j]==-1)
                continue;
            pfx[i+1]+= (memo[i][j]&2);
            pfx[i+v[j]]-= (memo[i][j]&2);
            memo[i+v[j]][j]|= (memo[i][j]&2)!=0;
        }
    }
    for (int i=1;i<n;i++)
        pfx[i]+=pfx[i-1];
    for (int i=0;i<n;i++)
    {
        if (pfx[i])
            memo[i][0]|=2;
    }
    for (int i=0;i<n;i++)
    {
        int a=0;
        for (int j=0;j<=k;j++)
        {
            if (memo[i][j]!=-1)
            {
                a|=memo[i][j];
            }
        }
        if (a==1)
            ans+='_';
        else if (a==2)
            ans+='X';
        else
            ans+='?';
    }
    return ans;
}
/*
const int S_MAX_LEN = 200 * 1000;
char buf[S_MAX_LEN + 1];
int main() {
    assert(1 == scanf("%s", buf));
    std::string s = buf;
    int c_len;
    assert(1 == scanf("%d", &c_len));
    std::vector<int> c(c_len);
    for (int i = 0; i < c_len; i++) {
        assert(1 == scanf("%d", &c[i]));
    }
    std::string ans = solve_puzzle(s, c);


    printf("%s\n", ans.data());
    return 0;
}

*/

• 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