Submission #739706

#	Time	Username	Problem	Language	Result	Execution time	Memory
739706		Jarif_Rahman	Paint By Numbers (IOI16_paint)	C++17	100 / 100	588 ms	31780 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

str solve_puzzle(str s, vector<int> c){
    int n = s.size(), k = c.size();
    if(n == 1){
        if(k == 0) return "_";
        return "X";
    }

    vector<int> B(n, 0), W(n, 0);

    for(int i = 0; i < n; i++){
        if(i) B[i] = B[i-1], W[i] = W[i-1];
        B[i]+=(s[i]=='X');
        W[i]+=(s[i]=='_');
    }

    auto black = [&](int l, int r){
        if(l > r) return false;
        return (B[r]-(l ? B[l-1]:0)) > 0;
    };
    auto white = [&](int l, int r){
        if(l > r) return false;
        return (W[r]-(l ? W[l-1]:0)) > 0;
    };

    vector<vector<bool>> dp1(n, vector<bool>(k, 0)), dp2 = dp1;

    for(int i = 0; i < n; i++) for(int j = 0; j < k; j++){
        if(i+1 < c[j]) continue;
        if(i && s[i] != 'X') dp1[i][j] = dp1[i-1][j];

        if(j == 0){
            dp1[i][j] = dp1[i][j]|(!white(i-c[j]+1, i) && !black(0, i-c[j]));
        }
        else{
            dp1[i][j] = dp1[i][j]|
                (!white(i-c[j]+1, i) && i-c[j]-1 >= 0 && s[i-c[j]] != 'X' && dp1[i-c[j]-1][j-1]);
        }
    }

    for(int i = n-1; i >= 0; i--) for(int j = k-1; j >= 0; j--){
        if(n-i < c[j]) continue;
        if(i != n-1 && s[i] != 'X') dp2[i][j] = dp2[i+1][j];

        if(j == k-1){
            dp2[i][j] = dp2[i][j]|(!white(i, i+c[j]-1) && !black(i+c[j], n-1));
        }
        else{
            dp2[i][j] = dp2[i][j]|
                (!white(i, i+c[j]-1) && i+c[j]+1 < n && s[i+c[j]] != 'X' && dp2[i+c[j]+1][j+1]);
        }
    }

    str ans(n, '?');
    for(int i = 0; i < n; i++) if(s[i] != '.') ans[i] = s[i];

    for(int i = 0; i < n; i++){
        if(ans[i] != '?') continue;

        if(i == 0){
            if(!dp2[i+1][0]) ans[i] = 'X';
            continue;
        }
        if(i == n-1){
            if(!dp1[i-1][k-1]) ans[i] = 'X';
            continue;
        }

        bool _ = 0;
        for(int j = 0; j <= k; j++){
            _|=((j == 0 ? !black(0, i-1):dp1[i-1][j-1]) & (j == k ? !black(i+1, n-1):dp2[i+1][j]));
        }
        if(!_) ans[i] = 'X';
    }

    vector<int> p(n, 0);
    for(int i = 0; i < n; i++) for(int j = 0; j < k; j++){
        if(j == 0 && black(0, i-1)) continue;
        if(j != 0 && (i < 2 || s[i-1] == 'X' || !dp1[i-2][j-1])) continue;
        if(n-i < c[j]) continue;

        bool ok = 0;
        if(j == k-1){
            ok|=(!white(i, i+c[j]-1) && !black(i+c[j], n-1));
        }
        else{
            ok|=(!white(i, i+c[j]-1) && i+c[j]+1 < n && s[i+c[j]] != 'X' && dp2[i+c[j]+1][j+1]);
        }
        if(!ok) continue;

        p[i]++;
        if(i+c[j] < n) p[i+c[j]]--;
    }

    int x = 0;
    for(int i = 0; i < n; i++){
        x+=p[i];
        if(ans[i] == '?' && x == 0) 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: 10 / 10