Submission #963620

#	Time	Username	Problem	Language	Result	Execution time	Memory
963620		hirayuu_oj	Paint By Numbers (IOI16_paint)	C++17	100 / 100	476 ms	262224 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
const ll INF=1LL<<60;
string to_string(string s){
    return s;
}
string to_string(char c){
    string ret="";
    ret+=c;
    return ret;
}
template<class S,class T>
string to_string(pair<S,T> x){
    string ret="("+to_string(x.first)+","+to_string(x.second)+")";
    return ret;
}
template<class S>
string to_string(S x){
    string ret="{";
    bool flg=0;
    for(auto i:x){
        if(flg)ret+=",";
        ret+=to_string(i);
        flg=1;
    }
    ret+="}";
    return ret;
}

void debug(){
    cerr<<"\n";
}
template<class S,class... T>
void debug(S x,T... y){
    cerr<<to_string(x)<<" ";
    debug(y...);
}
//#define DEBUG

#ifdef DEBUG
#define DBG(x...) cerr<<"DBG:";debug(x)
#else
#define DBG(x...)
#endif

std::string solve_puzzle(std::string s, std::vector<int> c) {
    string fin=s;
    s="_"+s+"_";
    DBG(s,c);
    int n=s.size();
    int m=c.size();
    vector<vector<int>> dp1(n,vector<int>(m+1,0));
    vector<vector<int>> dp2(n,vector<int>(m+1,0));
    rep(r,2){
        vector<int> cum(n+1,0);
        rep(i,n){
            cum[i+1]=cum[i];
            if(s[i]=='_')cum[i+1]++;
        }
        vector<vector<int>> dp(n,vector<int>(m+1,0));
        dp[0][0]=1;
        rep(i,n-1){
            rep(j,m+1){
                if(!dp[i][j])continue;
                if(s[i+1]!='X'){
                    dp[i+1][j]=1;
                }
                if(j==m)continue;
                if(i+c[j]+1<n&&s[i+c[j]+1]!='X'){
                    if(cum[i+c[j]+1]-cum[i+1]==0){
                        dp[i+c[j]+1][j+1]=1;
                    }
                }
            }
        }
        if(r==0)dp1=dp;
        else dp2=dp;
        reverse(all(s));
        reverse(all(c));
    }
    vector<int> cum(n+1,0);
    rep(i,n){
        cum[i+1]=cum[i];
        if(s[i]=='_')cum[i+1]++;
    }
    reverse(all(dp2));
    DBG(dp1,dp2);
    vector<int> ans(n,0);
    vector<vector<int>> dp(n,vector<int>(m+1,0));
    dp[0][0]=1;
    rep(i,n-1){
        rep(j,m+1){
            if(!dp[i][j])continue;
            if(s[i+1]!='X'){
                dp[i+1][j]=1;
            }
            if(j==m)continue;
            if(i+c[j]+1<n&&s[i+c[j]+1]!='X'){
                if(cum[i+c[j]+1]-cum[i+1]==0){
                    dp[i+c[j]+1][j+1]=1;
                    if(dp2[i+c[j]+1][m-(j+1)]){
                        ans[i+1]++;
                        ans[i+c[j]+1]--;
                    }
                }
            }
        }
    }
    rep(i,n-1){
        ans[i+1]+=ans[i];
    }
    vector<int> white(n);
    rep(i,n){
        rep(j,m+1){
            if(dp1[i][j]&&dp2[i][m-j]){
                white[i]=1;
            }
        }
    }
    rep(i,n-2){
        if(ans[i+1]&&white[i+1]){
            fin[i]='?';
        }
        else if(ans[i+1]){
            fin[i]='X';
        }
        else{
            fin[i]='_';
        }
    }
    return fin;
}

• 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