Submission #308990

#	Time	Username	Problem	Language	Result	Execution time	Memory
308990		vipghn2003	Paint By Numbers (IOI16_paint)	C++14	100 / 100	581 ms	44716 KiB

paint

#include<bits/stdc++.h>

using namespace std;

const int N=2e5+5;
int n,k,sum[N],f[N];
bool pref[N][105],suf[N][105];
bool canWhite[N],canBlack[N];

string solve_puzzle(string s,vector<int> cc)
{
    n=s.size();
    s="."+s;
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+(s[i]=='_');
    k=cc.size();
    vector<int>c(k+1);
    for(int i=0;i<k;i++) c[i+1]=cc[i];
    pref[0][0]=true;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=k;j++)
        {
            if(s[i]=='_') pref[i][j]=pref[i-1][j];
            else if(s[i]=='X')
            {
                if(j!=0&&i>=c[j]&&sum[i]-sum[i-c[j]]==0&&s[i-c[j]]!='X')
                {
                    if(i==c[j]) pref[i][j]=pref[i-c[j]][j-1];
                    else pref[i][j]=pref[i][j]=pref[i-c[j]-1][j-1];
                }
            }
            else
            {
                pref[i][j]=max(pref[i][j],pref[i-1][j]);
                if(j!=0&&i>=c[j]&&sum[i]-sum[i-c[j]]==0&&s[i-c[j]]!='X')
                {
                    if(i==c[j]) pref[i][j]=max(pref[i][j],pref[i-c[j]][j-1]);
                    else pref[i][j]=pref[i][j]=max(pref[i][j],pref[i-c[j]-1][j-1]);
                }
            }
        }
    }
    suf[n+1][k+1]=true;
    s+='.';
    for(int i=n;i>=1;i--)
    {
        for(int j=k+1;j>=1;j--)
        {
            if(s[i]=='_') suf[i][j]=suf[i+1][j];
            else if(s[i]=='X')
            {
                if(j!=k+1&&i+c[j]-1<=n&&sum[i+c[j]-1]-sum[i-1]==0&&s[i+c[j]]!='X')
                {
                    if(i+c[j]==n+1) suf[i][j]=suf[i+c[j]][j+1];
                    else  suf[i][j]=suf[i+c[j]+1][j+1];
                }
            }
            else
            {
                suf[i][j]=max(suf[i][j],suf[i+1][j]);
                if(j!=k+1&&i+c[j]-1<=n&&sum[i+c[j]-1]-sum[i-1]==0&&s[i+c[j]]!='X')
                {
                    if(i+c[j]==n+1) suf[i][j]=max(suf[i][j],suf[i+c[j]][j+1]);
                    else  suf[i][j]=max(suf[i][j],suf[i+c[j]+1][j+1]);
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='X') continue;
        for(int j=0;j<=k;j++)
        {
            canWhite[i]=max(canWhite[i],min(pref[i-1][j],suf[i+1][j+1]));
        }
    }
    for(int j=1;j<=k;j++)
    {
        memset(f,0,sizeof f);
        for(int i=1;i<=n-c[j]+1;i++)
        {
            if(sum[i+c[j]-1]-sum[i-1]!=0) continue;
            if(pref[max(0,i-2)][j-1]&&suf[min(n+1,i+c[j]+1)][j+1]&&s[i-1]!='X'&&s[i+c[j]]!='X')
            {
                f[i]++;
                f[i+c[j]]--;
            }
        }
        for(int i=1;i<=n;i++)
        {
            f[i]+=f[i-1];
            if(f[i]) canBlack[i]=true;
        }
    }
    string res;
    for(int i=1;i<=n;i++)
    {
        if(canWhite[i]&&canBlack[i]) res+='?';
        else if(canWhite[i]) res+='_';
        else res+='X';
    }
    return res;
}
/*
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin>>s;
    int k;
    cin>>k;
    vector<int>c(k);
    for(auto&x:c) cin>>x;
    cout<<solve_puzzle(s,c);
}
*/
/*
_.X_.._
2 2 2
*/

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:29:36: warning: operation on 'pref[i][j]' may be undefined [-Wsequence-point]
   29 |                     else pref[i][j]=pref[i][j]=pref[i-c[j]-1][j-1];
      |                          ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
paint.cpp:38:36: warning: operation on 'pref[i][j]' may be undefined [-Wsequence-point]
   38 |                     else pref[i][j]=pref[i][j]=max(pref[i][j],pref[i-c[j]-1][j-1]);
      |                          ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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