Submission #1150356

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150356		DobromirAngelov	Paint By Numbers (IOI16_paint)	C++20	100 / 100	403 ms	85828 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>

using namespace std;

const int MAXN=2e5+5;
const int MAXK=105;
const char X='X';
const char O='_';
const char P='*';

int n,k;
string s;
int c[MAXN];
bool dp[2][MAXN][MAXK];
bool dp1[MAXN][MAXK];
bool dp2[MAXN][MAXK];
int prefO[2][MAXN];
int posX[MAXN];

std::string solve_puzzle(std::string S, std::vector<int> C) 
{
    n=S.size();
    k=C.size();
    s='$'+S;
    for(int i=0;i<k;i++) c[i+1]=C[i];
    
    for(int t=0;t<2;t++)
    {   
        for(int i=1;i<=n;i++)
        {
            prefO[t][i]=prefO[t][i-1];
            if(s[i]==O) prefO[t][i]++;
        }
        for(int i=0;i<=n;i++)
        {
            if(s[i]!=X) dp[t][i][0]=1;
            else break;
        }
        for(int j=1;j<=k;j++)
        {
            dp[t][0][j]=0;
            for(int i=1;i<=n;i++)
            {
                if(i<c[j])
                {
                    dp[t][i][j]=0;
                }
                else if(i==c[j])
                {
                    if(j>=2 || prefO[t][i]>0) dp[t][i][j]=0;
                    else dp[t][i][j]=1;
                }
                else
                {
                    if(s[i]==O) dp[t][i][j]=dp[t][i-1][j];
                    else if(s[i]==X)
                    {
                        dp[t][i][j]=dp[t][i-c[j]-1][j-1];
                        if(prefO[t][i]-prefO[t][i-c[j]]>0 || s[i-c[j]]==X) dp[t][i][j]=0;
                    }
                    else
                    {
                        dp[t][i][j]|=dp[t][i-1][j];
                        bool tmp=dp[t][i-c[j]-1][j-1];
                        if(prefO[t][i]-prefO[t][i-c[j]]>0 || s[i-c[j]]==X) tmp=0;
                        dp[t][i][j]|=tmp;
                    }
                }
            }
        }

        reverse(c+1,c+k+1);
        reverse(s.begin()+1,s.begin()+n+1);
    }

    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=k;j++)
        {
            dp1[i][j]=dp[0][i][j];
            dp2[n-i+1][k-j+1]=dp[1][i][j];
        }
    }

    for(int i=1;i<=n;i++)
    {
        if(s[i]==X || s[i]==O) continue;
        for(int j=0;j<=k;j++)
        {
            if(dp1[i-1][j]==1 && dp2[i+1][j+1]==1)
            {
                s[i]=P;
                continue;
            }
        }
        if(s[i]!=P) s[i]=X;
    }

    for(int j=1;j<=k;j++)
    {
        for(int i=1;i<=n-c[j]+1;i++)
        {
            if(prefO[0][i+c[j]-1]-prefO[0][i-1]>0) continue;
            if(s[i-1]==X || s[i+c[j]]==X) continue;
            if(i==1 && j>1) continue;
            if(i==n-c[j]+1 && j<k) continue;
            if(i>1)
            {
                if(dp1[i-2][j-1]==0) continue;
            }
            if(i<n-c[j]+1)
            {
                if(dp2[i+c[j]+1][j+1]==0) continue;
            }
            posX[i]++;
            posX[i+c[j]]--;
        }
    }
    int cur=0;
    for(int i=1;i<=n;i++)
    {
        cur+=posX[i];
        if(s[i]!=P) continue;
        if(cur>0) s[i]='?';
        else s[i]=O;
    }

    for(int i=1;i<=n;i++) S[i-1]=s[i];
    return S;
}

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