Submission #1203418

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203418		vivkostov	Paint By Numbers (IOI16_paint)	C++20	100 / 100	477 ms	168408 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#include <cstdlib>
using namespace std;
int n,m,a[200005],dp[200005][105],rdp[200005][105],can[200005][2],p[200005];
char s[200005];
string otg;
void prec()
{
    for(int i=1;i<=n;i++)
    {
        p[i]=p[i-1];
        if(s[i]=='_')p[i]++;
    }
}
void make_dp()
{
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='X')break;
        dp[i][0]=1;
    }
    int last;
    dp[0][0]=1;
    for(int i=1;i<=m;i++)
    {
        last=0;
        for(int j=1;j<=n;j++)
        {
            if(s[j]=='_')last=j;
            if(s[j]=='_'||s[j]=='.')
            {
                dp[j][i]=dp[j-1][i];
            }
            if(s[j]=='X'||s[j]=='.')
            {
                if(last<=j-a[i]&&s[j-a[i]]!='X')
                {
                    if(i==1)dp[j][i]=max(dp[j][i],dp[j-a[i]][i-1]);
                    else dp[j][i]=max(dp[j][i],dp[j-a[i]-1][i-1]);
                }
            }
        }
    }
}
void make_rdp()
{
    for(int i=n;i>=1;i--)
    {
        if(s[i]=='X')break;
        rdp[i][m+1]=1;
    }
    rdp[n+1][m+1]=1;
    int last;
    for(int i=m;i>=1;i--)
    {
        last=n+1;
        for(int j=n;j>=1;j--)
        {
            if(s[j]=='_')last=j;
            if(s[j]=='_'||s[j]=='.')
            {
                rdp[j][i]=rdp[j+1][i];
            }
            if(s[j]=='X'||s[j]=='.')
            {
                if(last>=j+a[i]&&s[j+a[i]]!='X')
                {
                    if(i==m)rdp[j][i]=max(rdp[j][i],rdp[j+a[i]][i+1]);
                    else rdp[j][i]=max(rdp[j][i],rdp[j+a[i]+1][i+1]);
                }
            }
        }
    }
}
void resh()
{
    int to=1;
    s[0]='.';
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='_')
        {
            can[i][0]='_';
            continue;
        }
        for(int j=0;j<=m;j++)
        {
            if(s[i]!='X'&&dp[i-1][j]&&rdp[i+1][j+1])
            {
                can[i][0]=1;
            }
            if(j==m)break;
            if(j==0&&dp[i-1][j]&&rdp[i+a[j+1]+1][j+2]&&s[i-1]!='X'&&s[i+a[j+1]]!='X'&&p[i+a[j+1]-1]==p[i])
            {
                for(int z=max(to,i);z<i+a[j+1];z++)
                {
                    can[z][1]=1;
                }
                to=max(to,i+a[j+1]);
            }
            if(j==m-1&&dp[i-2][j]&&rdp[i+a[j+1]][j+2]&&s[i-1]!='X'&&s[i+a[j+1]]!='X'&&p[i+a[j+1]-1]==p[i])
            {
                for(int z=max(to,i);z<i+a[j+1];z++)
                {
                    can[z][1]=1;
                }
                to=max(to,i+a[j+1]);
            }
            if(dp[i-2][j]&&rdp[i+a[j+1]+1][j+2]&&s[i-1]!='X'&&s[i+a[j+1]]!='X'&&p[i+a[j+1]-1]==p[i])
            {
                for(int z=max(to,i);z<i+a[j+1];z++)
                {
                    can[z][1]=1;
                }
                to=max(to,i+a[j+1]);
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(can[i][0]&&can[i][1])otg+='?';
        else if(can[i][0])otg+='_';
        else otg+='X';
    }
}
string solve_puzzle(string S, vector<int> C)
{
    n=S.size();
    m=C.size();
    for(int i=1;i<=n;i++)
    {
        s[i]=S[i-1];
    }
    for(int i=1;i<=m;i++)
    {
        a[i]=C[i-1];
    }
    prec();
    make_dp();
    make_rdp();
    resh();
    return otg;
}

Compilation message (stderr)

paint.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
paint_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• 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