Submission #755313

#	Time	Username	Problem	Language	Result	Execution time	Memory
755313		alexander707070	Paint By Numbers (IOI16_paint)	C++14	90 / 100	2073 ms	27184 KiB

paint

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

char s[200007];
vector<int> c;
string ans;

bool pref[200007][107],li[200007][107];
bool suff[200007][107],li2[200007][107];
bool white,black;
int sum[200007],n,k;

bool ff(int pos,int k){
    if(k==-1 and pos<=0)return true;
    else if(pos<=0)return false;

    if(li[pos][k])return pref[pos][k];
    li[pos][k]=true;

    if(s[pos]!='X')pref[pos][k]=ff(pos-1,k);
    if(k>=0 and s[pos+1]!='X' and pos>=c[k] and sum[pos]-sum[pos-c[k]]==0 and s[pos-c[k]]!='X' and ff(pos-c[k]-1,k-1)){
        pref[pos][k]=true;
    }

    return pref[pos][k];
}

bool ff2(int pos,int k){
    if(k==c.size() and pos>=n+1)return true;
    else if(pos>=n+1)return false;

    if(li2[pos][k])return suff[pos][k];
    li2[pos][k]=true;

    if(s[pos]!='X')suff[pos][k]=ff2(pos+1,k);
    if(k<c.size() and s[pos-1]!='X' and pos+c[k]-1<=n and sum[pos+c[k]-1]-sum[pos-1]==0 and s[pos+c[k]]!='X' and ff2(pos+c[k]+1,k+1)){
        suff[pos][k]=true;
    }

    return suff[pos][k];
}

string solve_puzzle(string S, vector<int> C){
    c=C; n=int(S.size()); k=int(C.size());

    for(int i=1;i<=n;i++){
        s[i]=S[i-1]; sum[i]=sum[i-1];
        if(s[i]=='_')sum[i]++;
    }

    for(int i=1;i<=n;i++){
        if(s[i]!='.'){
            ans.push_back(s[i]); continue;
        }

        white=black=false;
        for(int f=-1;f<k;f++){
            if(ff(i-1,f) and ff2(i+1,f+1))white=true;
        }        
        
        for(int f=0;f<k;f++){
            for(int t=max(i-c[f]+1,1);t<=min(i,n-c[f]+1);t++){
                if(sum[t+c[f]-1]-sum[t-1]!=0 or s[t-1]=='X' or s[t+c[f]]=='X')continue;
                if(ff(t-2,f-1) and ff2(t+c[f]+1,f+1))black=true;
            }
        }

        if(white and black)ans.push_back('?');
        if(!white and black)ans.push_back('X');
        if(white and !black)ans.push_back('_');
    }

    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'bool ff2(int, int)':
paint.cpp:29:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     if(k==c.size() and pos>=n+1)return true;
      |        ~^~~~~~~~~~
paint.cpp:36:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     if(k<c.size() and s[pos-1]!='X' and pos+c[k]-1<=n and sum[pos+c[k]-1]-sum[pos-1]==0 and s[pos+c[k]]!='X' and ff2(pos+c[k]+1,k+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: 0 / 10