Submission #759011

#	Time	Username	Problem	Language	Result	Execution time	Memory
759011		dxz05	Paint By Numbers (IOI16_paint)	C++17	59 / 100	1 ms	340 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>

using namespace std;

vector<vector<bool>> get_dp(const string &s, const vector<int> &c){
    int n = (int) s.size(), k = (int) c.size();

    vector<int> pb(n), pw(n);

    for (int i = 0; i < n; i++){
        pb[i] = (i > 0 ? pb[i - 1] : 0) + (s[i] == 'X');
        pw[i] = (i > 0 ? pw[i - 1] : 0) + (s[i] == '_');
    }

    function<int(int, int, char)> get = [&](int l, int r, char c){
        int res = (c == 'B' ? pb[r] : pw[r]);
        if (l > 0) res -= (c == 'B' ? pb[l - 1] : pw[l - 1]);
        return res;
    };

    vector<vector<bool>> dp(n, vector<bool>(k, false));

    vector<vector<int>> can(k, vector<int>(n, 0));

    vector<int> last_x(n, -1);
    for (int i = 0; i < n; i++){
        if (s[i] == 'X'){
            last_x[i] = i;
        } else if (i > 0){
            last_x[i] = last_x[i - 1];
        }
    }

    for (int i = 0; i < n; i++){
        for (int j = 0; j < k; j++){
            if (i + 1 < c[j]) continue;

            int l = i - c[j] + 1;
            if (get(l, i, 'W') || l > 0 && s[l - 1] == 'X') continue;

            if (j == 0){
                if (l == 0 || last_x[l - 1] == -1) dp[i][j] = true;
                continue;
            }

            if (l < 2) continue;

            int ql = max(0, last_x[l - 2]), qr = l - 2;

            int df = can[j - 1][qr];
            if (ql > 0) can[j - 1][ql - 1];

            if (df > 0) dp[i][j] = true;
        }

        for (int j = 0; j < k; j++){
            can[j][i] = dp[i][j] + (i ? can[j][i - 1] : 0);
        }

    }

    return dp;
}

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

    string rs = string(s.rbegin(), s.rend());
    vector<int> rc = vector<int>(c.rbegin(), c.rend());

    vector<vector<bool>> ldp = get_dp(s, c);
    vector<vector<bool>> rdp = get_dp(rs, rc);

    reverse(rdp.begin(), rdp.end());

    vector<bool> black(n), white(n);
    for (int i = n - 1; i >= 0; i--){
        if (ldp[i][k - 1]){
            for (int t = i - c.back() + 1; t <= i; t++) black[t] = true;
            for (int t = i + 1; t < n; t++) white[t] = true;
        }
        if (s[i] == 'X') break;
    }

    for (int i = 0; i < n; i++){
        if (rdp[i][k - 1]){
            for (int t = i; t < i + c.front(); t++) black[t] = true;
            for (int t = 0; t < i; t++) white[t] = true;
        }
        if (s[i] == 'X') break;
    }

    for (int i = 0; i < n; i++){
        if (i + 1 < n && s[i + 1] == 'X') continue;
        for (int j = i + 2; j < n; j++){
            for (int p = 0; p + 1 < k; p++){
                int q = k - p - 2;
                if (!ldp[i][p] || !rdp[j][q]) continue;

                for (int t = i + 1; t < j; t++) white[t] = true;
                for (int t = i - c[p] + 1; t <= i; t++) black[t] = true;
                for (int t = j; t < j + c[p + 1]; t++) black[t] = true;
            }

            if (s[j] == 'X') break;
        }
    }

    string ans(n, '?');
    for (int i = 0; i < n; i++){
        if (s[i] != '.'){
            ans[i] = s[i];
            continue;
        }
        if (black[i] && !white[i]) ans[i] = 'X';
        if (!black[i] && white[i]) ans[i] = '_';
    }

    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::vector<std::vector<bool> > get_dp(const string&, const std::vector<int>&)':
paint.cpp:40:41: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   40 |             if (get(l, i, 'W') || l > 0 && s[l - 1] == 'X') continue;
      |                                   ~~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10