Submission #1192448

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192448		simona1230	Paint By Numbers (IOI16_paint)	C++20	59 / 100	0 ms	584 KiB

paint

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

int dp[200001][128][2];
int dp2[200001][128][2];
int b[200001];
int w[200001];
vector<int> pos[128];
int idx[128];
string solve_puzzle(string s, vector<int> c)
{
    int minn=s.size(),maxx=-1;
    int last=-1;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='_')last=i;
        if(s[i]=='X')minn=min(minn,i),maxx=i;
        for(int j=0;j<c.size();j++)
        {
            if(s[i]=='.'||s[i]=='X')
            {
                if(i+1>=c[j]&&last<=i-c[j])
                {
                    if(j==0)dp[i][j][1]=1;
                    else dp[i][j][1]=dp[i-c[j]][j-1][0];
                }
            }

            if(s[i]=='.'||s[i]=='_')
            {
                if(i!=0)
                {
                    dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]);
                }
            }
        }
    }

    last=s.size();
    for(int i=s.size();i>=0;i--)
    {
        if(s[i]=='_')last=i;
        for(int j=c.size()-1;j>=0;j--)
        {
            if(s[i]=='.'||s[i]=='X')
            {
                if(s.size()-i>=c[j]&&last>=i+c[j])
                {
                    if(j==c.size()-1)dp2[i][j][1]=1;
                    else dp2[i][j][1]=dp2[i+c[j]][j+1][0];
                }
            }

            if(s[i]=='.'||s[i]=='_')
            {
                if(i!=s.size()-1)
                {
                    dp2[i][j][0]=max(dp2[i+1][j][0],dp2[i+1][j][1]);
                }
            }
        }
    }

    for(int i=0;i<s.size();i++)
    {
        for(int j=0;j<c.size();j++)
        {
            if(j<c.size()-1&&dp[i][j][0]&&dp2[i][j+1][0]||j==c.size()-1&&dp[i][j][0]&&maxx<i)w[i]=1;
            if(dp[i][j][1]&&(j==c.size()-1&&maxx<=i||dp2[i+1][j+1][0]))pos[j].push_back(i);
            //cout<<i<<" "<<j<<" "<<dp2[i][j][0]<<" "<<dp2[i][j][1]<<endl;
        }
        if(minn>i&&dp2[i][0][0])w[i]=1;
    }

    for(int i=0;i<s.size();i++)
    {
        for(int j=0;j<c.size();j++)
        {
            while(idx[j]<pos[j].size()&&pos[j][idx[j]]<i)idx[j]++;
            if(idx[j]!=pos[j].size()&&pos[j][idx[j]]-c[j]+1<=i)b[i]=1;
        }
    }

    string ans="";
    for(int i=0;i<s.size();i++)
    {
        //cout<<i<<" "<<w[i]<<" "<<b[i]<<endl;
        if(w[i]&&b[i])ans+='?';
        else if(w[i])ans+='_';
        else ans+='X';
    }

    return ans;
}

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: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10