Submission #1013722

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013722		hotboy2703	Paint By Numbers (IOI16_paint)	C++17	100 / 100	146 ms	47272 KiB

paint

#include "paint.h"

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll MAXN = 2e5+100;
ll a[MAXN];
ll k,n;
bool pf[101][MAXN],sf[101][MAXN];
ll cnt_white[MAXN];
ll black[MAXN],white[MAXN];
string solve_puzzle(string s, vector<int> c) {
    k = sz(c);
    n = sz(s);
    c.insert(c.begin(),0);
    for (ll i = 1;i <= n;i ++){
        a[i] = s[i-1]=='X'?1:s[i-1]=='_'?0:-1;
        cnt_white[i] = a[i] == 0;
        cnt_white[i] += cnt_white[i-1];
    }
    pf[0][0] = 1;
    for (ll i = 1;i <= n; i++){
        if (a[i] == 1)break;
        pf[0][i] = 1;
    }
    for (ll i = 1;i <= k;i ++){
        for (ll j = c[i]+1;j <= n+1;j ++){
            if (j <= n && a[j]==1)continue;
            pf[i][j] = (cnt_white[j-1] - cnt_white[j-c[i]-1] > 0 ? 0 : pf[i-1][j-c[i]-1]) || pf[i][j-1];
        }
    }
    for (ll i = n+1;i >= 0;i --){
        if (a[i] == 1)break;
        sf[k][i] = 1;
    }
    for (ll i = k - 1;i >= 0;i --){
        for (ll j = n-c[i+1];j >= 0;j --){
            if (j&&a[j]==1)continue;
            sf[i][j] = (cnt_white[j+c[i+1]] - cnt_white[j] > 0 ? 0 : sf[i+1][j+c[i+1]+1]) || sf[i][j+1];
        }
    }
//    for (ll i = 0;i <= k;i ++){
//        for (ll j = 0;j <= n+1;j ++)cout<<pf[i][j]<<' ';
//        cout<<'\n';
//    }
//    cout<<'\n';
//    for (ll i = 0;i <= k;i ++){
//        for (ll j = 0;j <= n+1;j ++)cout<<sf[i][j]<<' ';
//        cout<<'\n';
//    }
//    cout<<pf[0][3]<<' '<<sf[0][3]<<'\n';
//    cout<<pf[1][3]<<' '<<sf[1][3]<<'\n';
//    cout<<pf[2][3]<<' '<<sf[2][3]<<'\n';
    for (ll j = 0;j <= k;j ++){
        for (ll i = 1;i <= n;i ++)white[i] |= pf[j][i] && sf[j][i];
        if (j==0)continue;
        for (ll i = 1;i + c[j] - 1 <= n;i ++){
            if (pf[j-1][i-1] && sf[j][i+c[j]] && cnt_white[i+c[j]-1]-cnt_white[i-1] == 0){
                black[i]++;
                black[i+c[j]]--;
            }
        }
    }
    for (ll i = 1;i <= n;i ++)black[i] += black[i-1];
    string ans;
    ans.resize(n);
    for (ll i = 0;i < n;i ++){
        if (black[i+1] && white[i+1])ans[i] = '?';
        else if (white[i+1])ans[i] = '_';
        else ans[i] = 'X';
    }
    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: 10 / 10