Submission #755242

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
755242	2023-06-09T16:07:54 Z	alexander707070	Shortcut (IOI16_shortcut)	C++14	Compilation error	0 ms	0 KB

shortcut

#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)return true;
    else if(pos<=0)return false;

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

    pref[pos][k]=ff(pos-1,k);
    if(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())return true;
    else if(pos>=n+1)return false;

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

    suff[pos][k]=ff(pos+1,k);
    if(pos+c[k]-1<=n and sum[pos+c[k]-1]-sum[pos]==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=0;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<=i;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

shortcut.cpp: In function 'bool ff2(int, int)':
shortcut.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())return true;
      |        ~^~~~~~~~~~
/usr/bin/ld: /tmp/cczVumML.o: in function `main':
grader.cpp:(.text.startup+0x124): undefined reference to `find_shortcut(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, int)'
collect2: error: ld returned 1 exit status