Submission #1238859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238859		erering	Paint By Numbers (IOI16_paint)	C++20	100 / 100	942 ms	493912 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
const int MAXN=2e5+5,MAXK=100+5;
#define pb push_back
int prefw[MAXN],prefb[MAXN],prelast[MAXN][MAXK],sufflast[MAXN][MAXK],last[MAXN][MAXK];
deque<int> prepos[MAXK],suffpos[MAXK];
vector<int> pos[MAXK];
std::string solve_puzzle(string s, vector<int> c) {
    for(int i=0;i<MAXN;i++){
        for(int j=0;j<MAXK;j++){
            prelast[i][j]=-1;
            sufflast[i][j]=-1;
            last[i][j]=2e9;
        }
    }
    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(i>0)prelast[i][j]=prelast[i-1][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)){
                prepos[j].pb(i);
                prelast[i][j]=i;
                continue;
            }
            if(j==0)continue;
            if(prepos[j-1].empty() || i-c[j]-1<0)continue;
            int it=prelast[i-c[j]-1][j-1];
            if(it==-1)continue;
            int b=prefb[i-c[j]]-prefb[it];
            if(b>0)continue;
            prepos[j].pb(i);
            prelast[i][j]=i;
        }
    }

    for(int i=s.size()-1;i>=0;i--){
        for(int j=c.size()-1;j>=0;j--){
            sufflast[i][j]=sufflast[i+1][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){
                suffpos[j].push_front(i);
                sufflast[i][j]=i;
                continue;
            }
            if(suffpos[j+1].empty())continue;
            int it=sufflast[i+c[j]+1][j+1];
            if(it==-1)continue;
            int b=prefb[it-1]-prefb[i+c[j]-1];
            if(b>0)continue;
            suffpos[j].push_front(i);
            sufflast[i][j]=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]);
                last[prepos[i][j]][i]=prepos[i][j];
                continue;
            }
            if(i==c.size()-1)continue;
            if(prepos[i][j]==s.size()-1 || s[prepos[i][j]+1]=='X')continue;
            int it=sufflast[prepos[i][j]+2][i+1];
            if(it==-1)continue;
            int b=prefb[it-1]-prefb[prepos[i][j]];
            if(b>0)continue;
            last[prepos[i][j]][i]=prepos[i][j];
            pos[i].pb(prepos[i][j]);
        }
    }
    for(int i=s.size()-2;i>=0;i--){
        for(int j=0;j<c.size();j++)last[i][j]=min(last[i][j],last[i+1][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++){
            if(i==0)continue;
            int it=prelast[i-1][j];
            if(it==-1)continue;
            if(prefb[i]-prefb[it]>0)continue;
            if(j==c.size()-1){
                if(prefb[s.size()-1]-prefb[it]==0)flagw=1;
                continue;
            }
            int it2=sufflast[i+1][j+1];
            if(it2==-1)continue;
            if(prefb[it2-1]-prefb[i]>0)continue;
            flagw=1;
        }
        int it3=sufflast[i+1][0];
        if(it3!=-1 && prefb[it3-1]==0)flagw=1;
        for(int j=0;j<c.size();j++){
            int it=last[i][j];
            if(it==2e9)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: 21 / 21
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10