Submission #57074

#	Time	Username	Problem	Language	Result	Execution time	Memory
57074		alenam0161	Paint By Numbers (IOI16_paint)	C++17	100 / 100	604 ms	129840 KiB

paint

    #include "paint.h"
    #include <cstdlib>
    #include <bits/stdc++.h>
    using namespace std;
    const int N = 300007;
    const int K = 307;
    bool suf[N][K];
    bool pre[N][K];
    int gum[N];
    int vl[N];
    int g[N];
    std::string solve_puzzle(std::string s, std::vector<int> c) {
        int n=s.length();
        int k=c.size();
        for(int i=0;i<n;++i){
            if(i)gum[i]+=gum[i-1];
            gum[i]+=(s[i]=='_');
        }
        auto sum=[&](int l,int r){
            return gum[r]-(l==0 ? 0:gum[l-1]);
        };
        suf[n][k]=true;
        suf[n+1][k]=true;
        for(int i=n-1;i>=0;i--){
            for(int j=k;j>=0;--j){
                if(s[i]!='X'&&suf[i+1][j])suf[i][j]=true;
                if(j==k)continue;
                if(c[j]+i-1<n&&sum(i,i+c[j]-1)==0){
                    if(i+c[j]<n&&s[i+c[j]]=='X')continue;
                    if(suf[i+c[j]+1][j+1]==false)continue;
                    suf[i][j]=true;
                }
            }
        }
        for(int i=0;i<n;++i){
            for(int j=-1;j<k;++j){
                int z=(i==0&&j==-1);
                if(s[i]!='X'&&z)pre[0][0]=true;
                if(s[i]!='X'&&z==false&&pre[i-1][j+1]==true)pre[i][j+1]=true;
                if(j==-1)continue;
                if(i-c[j]+1>=0&&sum(i-c[j]+1,i)==0){
                    if(i-c[j]>=0&&s[i-c[j]]=='X')continue;
                    if(i-c[j]-1<0&&j!=0)continue;
                    if(i-c[j]-1>=0&&pre[i-c[j]-1][j]==false)continue;
                    pre[i][j+1]=true;
                }
            }
        }
        for(int i=0;i<n;++i){
            for(int j=-1;j<k;++j){
                if(s[i]!='.')continue;
                bool okl=false;
                bool okr=false;
                if(suf[i+1][j+1]==true)okr=true;
                okl=(i==0&&j==-1)||(!(i==0&&j==-1)&&pre[i-1][j+1]);
                if(okr&&okl)vl[i]|=1;
            }
        }
        for(int i=0;i<n;++i){
            for(int j=0;j<k;++j){
                if(s[i]=='_')continue;
                bool ok=false;
                if(c[j]+i-1<n){
                    bool x=true;
                    if(i>0){
                        if(s[i-1]=='X')x=false;
                        else if(i-2>=0){
                        if(pre[i-2][j]==false){
                            x=false;
                        }
                        }
                        else if(j!=0)x=false;
                    }
                    else if(j!=0)x=false;
                    if(x==false)continue;
                    if(c[j]+i==n){
                        if(pre[c[j]+i-1][j+1]==true&&j==k-1&&sum(i,c[j]+i-1)==0)
                            g[i]=max(g[i],c[j]);
                    }
                    else
                    if(pre[c[j]+i-1][j+1]==true&&suf[c[j]+i+1][j+1]==true&&s[c[j]+i]!='X'&&sum(i,c[j]+i-1)==0){
                        g[i]=max(g[i],c[j]);
                    }
                }
            }
        }

        for(int i=0;i<n;++i){
            if(g[i]>0)vl[i]|=2;
            g[i+1]=max(g[i+1],g[i]-1);
        }
        for(int i=0;i<n;++i){
            if(s[i]=='.'){
                if(vl[i]==0)assert(0);
                if(vl[i]==1)s[i]='_';
                if(vl[i]==2)s[i]='X';
                if(vl[i]==3)s[i]='?';
            }
        }
        return s;
    }

Compilation message (stderr)

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:62:22: warning: unused variable 'ok' [-Wunused-variable]
                 bool ok=false;
                      ^~

• 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