Submission #792050

#	Time	Username	Problem	Language	Result	Execution time	Memory
792050		alvingogo	Paint By Numbers (IOI16_paint)	C++14	90 / 100	2100 ms	406936 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

string solve_puzzle(string s, vector<int> c) {
    int n=s.size(),k=c.size();
    string ans=s;
    vector<int> nb(n),nw(n),pb(n),pw(n);
    int rb=n,rw=n;
    for(int i=n-1;i>=0;i--){
        if(s[i]=='X'){
            rb=i;
        }
        else if(s[i]=='_'){
            rw=i;
        }
        nb[i]=rb;
        nw[i]=rw;
    }
    int lb=-1,lw=-1;
    for(int i=0;i<n;i++){
        if(s[i]=='X'){
            lb=i;
        }
        else if(s[i]=='_'){
            lw=i;
        }
        pb[i]=lb;
        pw[i]=lw;
    }
    vector<set<int> > dp(k);
    for(int i=0;i<k;i++){
        for(int j=0;j+c[i]-1<n;j++){
            if(i==0){
                if((j==0 || pb[j-1]==-1) && nw[j]>=(j+c[i])){
                    dp[i].insert(j);
                }
            }
            else{
                if(nw[j]<j+c[i]){
                    continue;
                }
                auto h=dp[i-1].upper_bound(j-1-c[i-1]);
                if(h==dp[i-1].begin()){
                    continue;
                }
                if((*prev(h))+c[i-1]>(j==0?-1:pb[j-1])){
                    dp[i].insert(j);
                }
            }
        }
    }
    
    for(int i=k-1;i>=0;i--){
        vector<int> z;
        if(i==k-1){
            for(auto h:dp[i]){
                if(h+c[i]<n && nb[h+c[i]]<n){
                    z.push_back(h);
                }
            }
        }
        else{
            for(auto h:dp[i]){
                auto u=dp[i+1].lower_bound(h+c[i]+1);
                if(u==dp[i+1].end() || (*u)>nb[h+c[i]]){
                    z.push_back(h);
                }
            }
        }
        for(auto h:z){
            dp[i].erase(h);
        }
    }
    for(int i=0;i<n;i++){
        int f=0;
        for(int j=0;j<k;j++){
            auto h=dp[j].upper_bound(i);
            if(h!=dp[j].begin() && *prev(h)>i-c[j]){
                f|=1;
                break;
            }
        }
        auto d=*dp[0].rbegin();
        if(i<d){
            f|=2;
        }
        for(int j=1;j<k;j++){
            auto e=dp[j].upper_bound(i);
            if(e==dp[j].end()){
                continue;
            }
            auto g=dp[j-1].upper_bound(i-c[j-1]);
            if(g==dp[j-1].begin()){
                continue;
            }
            g=prev(g);
            if(nb[(*g)+c[j-1]]>=(*e)){
                f|=2;
                break;
            }
        }
        auto e=*dp[k-1].begin();
        if(i>=e+c[k-1]){
            f|=2;
        }
        if(f==1){
            ans[i]='X';
        }
        else if(f==2){
            ans[i]='_';
        }
        else{
            ans[i]='?';
        }
    }
    return ans;
}

• 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