Submission #1302830

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302830		Mamikonm1	Paint By Numbers (IOI16_paint)	C++17	7 / 100	1 ms	348 KiB

paint

#include "paint.h"
#include <bits//stdc++.h>
using namespace std;
#define V vector
#define pb push_back
const int N=100;
std::string solve_puzzle(std::string s, std::vector<int> c) {
    int n=s.size(),k=c.size();
    V<bitset<N+1>>dp1(n),dp2(n);
    dp1[0][0]=(s[0]!='X');
    dp2[n-1][0]=(s[n-1]!='X');
    V<int>mek(n),zr(n);
    V<bool>ka(n);
    zr[0]=(s[0]=='_');
    for(int i=1;i<n;++i)zr[i]=zr[i-1]+(s[i]=='_');
    ka[n-1]=(s[n-1]=='X');
    for(int i=n-2;i>=0;--i)ka[i]=ka[i+1] or (s[i]=='X');
    string ans;
    bool d,de,zro;
    for(int i=0;i<n;++i){
        if(i and s[i]!='X')dp1[i]|=dp1[i-1];
        if(i and s[i-1]=='X')continue;
        for(int j=0;j<k;++j){
            d=0;
            if(i<2)d=!j;
            else d=dp1[i-2][j];
   //         if(i==0)cout<<d<<'\n';
            if(i+c[j]-1>=n or !d)continue;
            if(zr[i+c[j]-1]-(i?zr[i-1]:0))continue;
            if(i+c[j]<n and s[i+c[j]]=='X')continue;
            dp1[i+c[j]-1][j+1]=1;
            if(j==k-1 and (i+c[j]==n or !ka[i+c[j]])){
                mek[i]++;
                if(i+c[j]<n)mek[i+c[j]]--;
            }
        }
    }
 //   assert(dp1[n-2][1]);
    for(int i=n-1;i>=0;--i){
        if(i+1<n and s[i]!='X')dp2[i]|=dp2[i+1];
        if(i+1<n and s[i+1]=='X')continue;
        for(int j=0;j<k;++j){
            d=0;
            if(i+2>=n)d=!j;
            else d=dp2[i+2][j];
            if(i-c[k-j-1]+1<0 or !d)continue;
            if(zr[i]-(i-c[k-j-1]?zr[i-c[k-j-1]-1]:0))continue;
            if(i-c[k-j-1]>=0 and s[i-c[k-j-1]]=='X')continue;
            dp2[i-c[k-j-1]+1][j+1]=1;
            de=0;
            if(i-c[k-j-1]-1<0)de=!(k-j-1);
            else de=dp1[i-c[k-j-1]-1][k-j-1];
            if(de){
                mek[i-c[k-j-1]+1]++;
                if(i+1<n)mek[i+1]--;
            }
        }
    }
    for(int i=0;i<n;++i){
        if(i)mek[i]+=mek[i-1];
        if(s[i]!='.'){
            ans.pb(s[i]);
            continue;
        }
        zro=0;
        for(int j=0;j<=k;++j){
            d=de=0;
            if(!i)d=!j;
            else d=dp1[i-1][j];
            if(i==n-1)de=!(k-j);
            else de=dp2[i+1][k-j];
            if(d and de){
                zro=1;
                break;
            }
        }
        if(zro and mek[i])ans.pb('?');
        else if(zro)ans.pb('_');
        else ans.pb('X');
     //   cout<< zro<<' '<<mek[i] <<'\n';
        assert(zro or mek[i]);
    }
    return ans;
}

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: 0 / 3
• Subtask 3: 0 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10