Submission #622545

#	Time	Username	Problem	Language	Result	Execution time	Memory
622545		Lucpp	Paint By Numbers (IOI16_paint)	C++17	100 / 100	610 ms	29724 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;

int n, k;
string s;
vector<int> c;

vector<vector<bool>> calc(){
    vector<vector<bool>> dp(n+1, vector<bool>(k+1, false));
    dp[0][0] = true;
    for(int i = 0; i < n; i++){
        if(s[i] == 'X') break;
        dp[i+1][0] = true;
    }
    int last_ = -1;
    for(int i = 0; i < n; i++){
        if(s[i] == '_') last_ = i;
        for(int j = 0; j < k; j++){
            int start = i+1-c[j];
            if(start > last_){
                if(start > 0) dp[i+1][j+1] = dp[start-1][j] && s[start-1] != 'X';
                else if(j == 0) dp[i+1][j+1] = true;
            }
            if(s[i] != 'X') dp[i+1][j+1] = dp[i+1][j+1] || dp[i][j+1];
        }
    }
    return dp;
}

string solve_puzzle(string S, vector<int> C){
    s = S;
    c = C;
    n = (int)S.size();
    k = (int)C.size();
    auto dp1 = calc();
    reverse(s.begin(), s.end());
    reverse(c.begin(), c.end());
    auto dp2 = calc();
    reverse(s.begin(), s.end());
    reverse(c.begin(), c.end());
    string ans(n, ' ');
    vector<bool> w(n), b(n);
    for(int h = 0; h <= k; h++){
        vector<bool> is_valid(n);
        if(h > 0){
            int under = 0;
            for(int i = 0; i < c[h-1]; i++){
                if(s[i] == '_') under++;
            }
            for(int i = 0; i+c[h-1]-1 < n; i++){
                if(under == 0){
                    bool le = (i == 0 && h == 1) || (i > 0 && s[i-1] != 'X' && dp1[i-1][h-1]);
                    bool ri = (i == n-c[h-1] && h == k) || (i < n-c[h-1] && s[i+c[h-1]] != 'X' && dp2[n-1-i-c[h-1]][k-h]);
                    is_valid[i] = le && ri;
                }
                if(i+c[h-1] < n && s[i+c[h-1]] == '_') under++;
                if(s[i] == '_') under--;
            }
        }
        int valid = 0;
        for(int i = 0; i < n; i++){
            valid += is_valid[i];
            if(h > 0 && i >= c[h-1]) valid -= is_valid[i-c[h-1]];
            if(s[i] == '.'){
                if(dp1[i][h] && dp2[n-i-1][k-h]) w[i] = true;
                if(h > 0 && valid > 0) b[i] = true;
            }
        }
    }
    for(int i = 0; i < n; i++){
        if(s[i] != '.') ans[i] = s[i];
        else{
            if(w[i] && b[i]) ans[i] = '?';
            else ans[i] = w[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