Submission #532466

#	Time	Username	Problem	Language	Result	Execution time	Memory
532466		perchuts	Paint By Numbers (IOI16_paint)	C++17	100 / 100	534 ms	33256 KiB

paint

#include <bits/stdc++.h>
#define maxn (int)(1e5+51)
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define ll long long
#define pb push_back
#define ull unsigned long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define inf 2000000001
#define mod 1000000007 //998244353
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#include "paint.h"
using namespace std;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

vector<vector<bool>> solvedp(vector<int>w,vector<int>b,vector<int>c){
    int n = sz(w), k = sz(c);
    vector<int>wpref(n+1);
    for(int i=1;i<=n;++i)wpref[i]=wpref[i-1]+w[i-1];
    vector<vector<bool>>dp(n+1,vector<bool>(k+1,0));
    dp[0][0] = true;

    for(int i=1;i<=n;++i)dp[i][0] = dp[i-1][0]&&!b[i-1];

    for(int j=1;j<=k;++j){
        for(int i=1;i<=n;++i){
            if(!b[i-1]){
                if(dp[i-1][j])dp[i][j] = true;
            }
            if(!w[i-1]){
                if(c[j-1] > i)continue;
                if(wpref[i]-wpref[i-c[j-1]] > 0)continue;
                if(i!=c[j-1]&&b[i-c[j-1]-1])continue;
                if(dp[max(0,i-c[j-1]-1)][j-1])dp[i][j] = true;
            }
        }
    }
    return dp;
}

string solve_puzzle(string s,vector<int>c){
    int n = sz(s), k = sz(c);

    vector<int>w(n), b(n);

    for(int i=0;i<n;++i)w[i] = (s[i]=='_');
    for(int i=0;i<n;++i)b[i] = (s[i]=='X');
    vector<vector<bool>>prefixdp = solvedp(w,b,c);

    reverse(all(b));reverse(all(w));reverse(all(c));

    vector<vector<bool>>suffixdp = solvedp(w,b,c);

    reverse(all(b));reverse(all(w));reverse(all(c));

    // for(int j=0;j<=k;++j)   
    //     for(int i=1;i<=n;++i)
    //         cout<<prefixdp[i][j]<<" \n"[i==n];

    // for(int j=0;j<=k;++j)   
    //     for(int i=1;i<=n;++i)
    //         cout<<suffixdp[i][j]<<" \n"[i==n];

    vector<bool>canwhite(n),canblack(n);
    
    for (int i=0; i<n; ++i) for (int j=0; j<=k; ++j) 
    if (!b[i] && prefixdp[i][j] && suffixdp[n-i-1][k-j]) canwhite[i] = true;

    vector<int>intervals(n+1);
    vector<int>wpref(n+1);
    
    for(int i=1;i<=n;++i)wpref[i] = wpref[i-1] + w[i-1];

    for (int j=0; j<k; ++j) {
        for (int start=0; start+c[j]<=n; ++start) {
            if (start > 0 && b[start-1]) continue;
            if (start+c[j]<n && b[start+c[j]]) continue;
            if (wpref[start+c[j]] > wpref[start]) continue;
            if (prefixdp[max(0,start-1)][j] && suffixdp[max(0,n-start-c[j]-1)][k-j-1]) {
                intervals[start] += 1;
                intervals[start+c[j]] -= 1;
            }
        }
    }

    // cout<<"alive"<<endl;
    int sum = 0;

    for(int i=0;i<n;++i){
        sum += intervals[i];
        if(sum>0)canblack[i] = true;
    }
    for(int i=0;i<n;++i){
        // cout<<canblack[i]<<" "<<canwhite[i]<<endl;
        if(canblack[i]&&canwhite[i])s[i]='?';
        else if(canblack[i])s[i]='X';
        else s[i]='_';
    }

    return s;

}

// int main(){
//     string s;int k;cin>>s>>k;
//     vector<int>c(k);
//     for(auto& x:c)cin>>x;
//     cout<<solve_puzzle(s,c)<<endl;
// }

• 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