Submission #1192325

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

paint

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


int p[200001],in[200001];
int dp[5001][5001][2];
int p2[200001],in2[200001];
int dp2[5001][5001][2];
int b[200001];
int w[200001];
string solve_puzzle(string s, vector<int> c)
{
    in[0]=1;
    p[0]=c[0];
    in[c[0]]=1;
    for(int i=1;i<c.size();i++)
        p[i]=p[i-1]+c[i],in[p[i]]=1;

    in2[0]=1;
    p2[c.size()-1]=c[c.size()-1];
    in2[c[c.size()-1]]=1;
    for(int i=c.size()-2;i>=0;i--)
        p2[i]=p2[i+1]+c[i],in2[p2[i]]=1;

    for(int i=0;i<s.size();i++)
    {
        for(int j=0;j<=i+1;j++)
        {
            if(in[j]&&(s[i]=='_'||s[i]=='.'))
            {
                //cout<<"in"<<endl;
                if(i==0)dp[i][j][0]=1;
                else dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]);
            }

            if(j&&(s[i]=='X'||s[i]=='.'))
            {
                if(in[j-1])
                {
                    if(i==0)dp[i][j][1]=1;
                    else dp[i][j][1]=dp[i-1][j-1][0];
                }
                else
                {
                    dp[i][j][1]=dp[i-1][j-1][1];
                }
            }

            //cout<<i<<" "<<j<<" - "<<dp[i][j][0]<<" "<<dp[i][j][1]<<endl;

        }
    }

    for(int i=s.size()-1;i>=0;i--)
    {
        for(int j=0;j<=s.size()-i;j++)
        {
            if(in2[j]&&(s[i]=='_'||s[i]=='.'))
            {
                if(i==s.size()-1)dp2[i][j][0]=1;
                else dp2[i][j][0]=max(dp2[i+1][j][0],dp2[i+1][j][1]);
            }

            if(j&&(s[i]=='X'||s[i]=='.'))
            {
                if(in2[j-1])
                {
                    if(i==s.size()-1)dp2[i][j][1]=1;
                    else dp2[i][j][1]=dp2[i+1][j-1][0];
                }
                else
                {
                    dp2[i][j][1]=dp2[i+1][j-1][1];
                }
            }
            //cout<<i<<" "<<j<<" - "<<dp2[i][j][0]<<" "<<dp2[i][j][1]<<endl;
        }
    }

    for(int i=0;i<s.size();i++)
    {
        for(int j=0;j<c.size();j++)
        {
            for(int l=1;l<=c[j];l++)
            {
                int h=0;
                if(j)h=p[j-1];
                h+=l;

                int h2=0;
                if(j!=c.size()-1)h2=p2[j+1];
                h2+=(c[j]-l+1);

                if(dp[i][h][1]&&dp2[i][h2][1])b[i]=1;
            }

            if(dp[i][p[j]][0]&&(j==c.size()-1&&dp2[i][0][0]||dp2[i][p2[j+1]][0]))w[i]=1;
        }

        if(dp[i][0][0]&&dp2[i][p2[0]][0])w[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: 0 / 7
• Subtask 2: 0 / 3
• Subtask 3: 0 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10