Submission #759093

#	Time	Username	Problem	Language	Result	Execution time	Memory
759093		dxz05	Paint By Numbers (IOI16_paint)	C++17	100 / 100	1146 ms	182944 KiB

paint

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

using namespace std;

vector<bitset<100>> 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<bitset<100>> dp(n);

    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' || i + 1 < n && s[i + 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) df -= 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<bitset<100>> ldp = get_dp(s, c);
    vector<bitset<100>> rdp = get_dp(rs, rc);

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

    vector<vector<int>> pl(n, vector<int>(k, 0));
    vector<vector<int>> pr(n, vector<int>(k, 0));
    for (int i = 0; i < n; i++){
        for (int j = 0; j < k; j++){
            pl[i][j] = ldp[i][j];
            pr[i][j] = rdp[i][j];
            if (i){
                pl[i][j] += pl[i - 1][j];
                pr[i][j] += pr[i - 1][j];
            }
        }
    }

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

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

    vector<int> black(n, 0), white(n, 0);

    function<void(int, int)> paint_it_black = [&](int l, int r){
        if (l < n) black[l]++;
        if (r + 1 < n) black[r + 1]--;
    };

    function<void(int, int)> paint_it_white = [&](int l, int r){
        if (l < n) white[l]++;
        if (r + 1 < n) white[r + 1]--;
    };

    for (int i = n - 1; i >= 0; i--){
        if (ldp[i][k - 1]){
            paint_it_black(i - c.back() + 1, i);
            paint_it_white(i + 1, n - 1);
        }
        if (s[i] == 'X') break;
    }

    for (int i = 0; i < n; i++){
        if (rdp[i][k - 1]){
            paint_it_black(i, i + c.front() - 1);
            paint_it_white(0, i - 1);
        }
        if (s[i] == 'X') break;
    }

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

            int qr = right_x[i + 1];
            if (qr == -1) qr = n - 1;

            if (pr[qr][q] - pr[i + 1][q] > 0){
                paint_it_black(i - c[p] + 1, i);
            }

        }
    }

    for (int i = 1; i + 1 < n; i++){
        if (s[i] != '.') continue;
        int xl = left_x[i], xr = right_x[i];
        if (xl == -1) xl = 0;
        if (xr == -1) xr = n - 1;

        for (int p = 0; p + 1 < k; p++){
            int q = k - p - 2;

            int df = pl[i - 1][p];
            if (xl) df -= pl[xl - 1][p];

            if (df <= 0) continue;

            df = pr[xr][q];
            df -= pr[i][q];

            if (df > 0) paint_it_white(i, i);
        }

    }

    string ans(n, '?');
    for (int i = 0; i < n; i++){
        if (i){
            black[i] += black[i - 1];
            white[i] += white[i - 1];
        }

        if (s[i] != '.'){
            ans[i] = s[i];
            continue;
        }
        if (black[i] && !white[i]) ans[i] = 'X';
        if (!black[i] && white[i]) ans[i] = '_';
        assert(black[i] || white[i]);
    }

    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::vector<std::bitset<100> > 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' || i + 1 < n && s[i + 1] == 'X') continue;
      |                                   ~~~~~~^~~~~~~~~~~~~~~~~~
paint.cpp:40:73: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   40 |             if (get(l, i, 'W') || l > 0 && s[l - 1] == 'X' || i + 1 < n && s[i + 1] == 'X') continue;
      |                                                               ~~~~~~~~~~^~~~~~~~~~~~~~~~~~

• 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