Submission #1238835

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238835		erering	Paint By Numbers (IOI16_paint)	C++20	59 / 100	1 ms	584 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
const int MAXN=2e5+5,MAXK=100+5;
#define pb push_back
bool prefdp[MAXN][MAXK],suffdp[MAXN][MAXK];
int prefw[MAXN],prefb[MAXN];
deque<int> prepos[MAXK],suffpos[MAXK];
vector<int> pos[MAXK];
std::string solve_puzzle(string s, vector<int> c) {
    for(int i=0;i<s.size();i++){
        if(s[i]=='X')prefb[i]++;
        if(s[i]=='_')prefw[i]++;
        if(i>0){
            prefw[i]+=prefw[i-1];
            prefb[i]+=prefb[i-1];
        }
    }

    for(int i=0;i<s.size();i++){
        for(int j=0;j<c.size();j++){
            if(c[j]>i+1)continue;
            int w=prefw[i]-(i-c[j]>=0?prefw[i-c[j]]:0);
            if(w>0)continue;
            if(j==0 && (i-c[j]<0 || prefb[i-c[j]]==0)){
                prefdp[i][j]=1;
                prepos[j].pb(i);
                continue;
            }
            if(prepos[j-1].empty())continue;
            auto it=lower_bound(prepos[j-1].begin(),prepos[j-1].end(),i-c[j]);
            if(it==prepos[j-1].begin())continue;
            it--;
            int b=prefb[i-c[j]]-prefb[*it];
            if(b>0)continue;
            prefdp[i][j]=1;
            prepos[j].pb(i);
        }
    }

    for(int i=s.size()-1;i>=0;i--){
        for(int j=c.size()-1;j>=0;j--){
            if(c[j]>s.size()-i)continue;
            int w=prefw[i+c[j]-1]-(i>0?prefw[i-1]:0);
            if(w>0)continue;
            if(j==c.size()-1 && prefb[s.size()-1]-prefb[i+c[j]-1]==0){
                suffdp[i][j]=1;
                suffpos[j].push_front(i);
                continue;
            }
            if(suffpos[j+1].empty())continue;
            auto it=upper_bound(suffpos[j+1].begin(),suffpos[j+1].end(),i+c[j]);
            if(it==suffpos[j+1].end())continue;
            int b=prefb[(*it)-1]-prefb[i+c[j]-1];
            if(b>0)continue;
            suffdp[i][j]=1;
            suffpos[j].push_front(i);
        }
    }

    for(int i=0;i<c.size();i++){
        for(int j=0;j<prepos[i].size();j++){
            if(i==c.size()-1 && prefb[s.size()-1]-prefb[prepos[i][j]]==0){
                pos[i].pb(prepos[i][j]);
                continue;
            }
            if(i==c.size()-1)continue;
            if(prepos[i][j]==s.size()-1 || s[prepos[i][j]+1]=='X')continue;
            auto it=upper_bound(suffpos[i+1].begin(),suffpos[i+1].end(),prepos[i][j]+1);
            if(it==suffpos[i+1].end())continue;
            int b=prefb[(*it)-1]-prefb[prepos[i][j]];
            if(b>0)continue;
            pos[i].pb(prepos[i][j]);
        }
    }
    string ans;
    for(int i=0;i<s.size();i++){
        if(s[i]!='.'){
            ans+=s[i];
            continue;
        }
        bool flagb=0,flagw=0;
        for(int j=0;j<c.size();j++){
            auto it=lower_bound(prepos[j].begin(),prepos[j].end(),i);
            if(it==prepos[j].begin())continue;
            it--;
            if(prefb[i]-prefb[*it]>0)continue;
            if(j==c.size()-1){
                flagw=1;
                continue;
            }
            auto it2=upper_bound(suffpos[j+1].begin(),suffpos[j+1].end(),i);
            if(it2==suffpos[j+1].end())continue;
            if(prefb[*it2]-prefb[i]>0)continue;
            flagw=1;
        }
        auto it3=upper_bound(suffpos[0].begin(),suffpos[0].end(),i);
        if(it3!=suffpos[0].end() && prefb[*it3-1]==0)flagw=1;
        for(int j=0;j<c.size();j++){
            auto it=lower_bound(pos[j].begin(),pos[j].end(),i);
            if(it==pos[j].end())continue;
            if((*it)-c[j]+1<=i){
                flagb=1;
            }
        }
        if(flagb && flagw)ans+='?';
        else if(flagb)ans+='X';
        else ans+='_';
    }
    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: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10