Submission #581598

#	Time	Username	Problem	Language	Result	Execution time	Memory
581598		SlavicG	Paint By Numbers (IOI16_paint)	C++17	100 / 100	815 ms	175948 KiB

paint

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

#define sz(a) (int)a.size()
#define pb push_back
#define all(a) a.begin(),a.end()
using ll = long long;
using namespace std;

int query(int l, int r, vector<int>& p) {
    assert(l >= 0 && r >= 0 && l < sz(p) && r < sz(p));
    assert(l <= r);
    return p[r] - (l ? p[l - 1]: 0);
}

vector<vector<int>> calc(string s, vector<int> c) {
    int n = sz(s), k = sz(c);
    vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
    vector<int> black(n + 1, 0), white(n + 1, 0);
    dp[0][0] = 1;
    for(int i = 0; i < n; ++i) {
        black[i + 1] = black[i] + (s[i] == 'X');
        white[i + 1] = white[i] + (s[i] == '_');
        if(!black[i + 1]) dp[i + 1][0] = 1;
    }

    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= k; ++j) {
            if(s[i - 1] == 'X' || s[i - 1] == '.') {
                int p = i - c[j - 1];
                if(p - (j != 1) < 0 || query(p + 1, i, white) || query(p, p, black)) {
                    //Purice Chad
                } else dp[i][j] |= dp[p - (j != 1)][j - 1];
            }
            if(s[i - 1] == '_' || s[i - 1] == '.') {
                dp[i][j] |= dp[i - 1][j];
            }
        }
    }
    return dp;
}

string solve_puzzle(string s, vector<int> c) {
    int n = sz(s), k = sz(c);
    vector<vector<int>> pref_dp = calc(s, c);
    reverse(all(s)), reverse(all(c));
    vector<vector<int>> suf_dp = calc(s, c);
    reverse(all(s)), reverse(all(c));
    vector<int> white(n + 5, 0), black(n + 5, 0);
    for(int i = 0; i < n; ++i) {
        white[i + 1] = white[i] + (s[i] == '_');
        black[i + 1] = black[i] + (s[i] == 'X');
    }
    white[n + 1] += white[n];
    white[n + 2] += white[n + 1];
    black[n + 1] += black[n];
    black[n + 2] += black[n + 1];
    vector<bool> can_white(n + 5, false);

    for(int i = 1; i <= n; ++i) {
        for(int j = 0; j <= k; ++j) {
            if(j == k && i == n) {
                if(pref_dp[i - 1][j] && s[i - 1] != 'X') can_white[i] = true;
                continue;
            }
            if(i == n) continue;
            if(pref_dp[i - 1][j] && suf_dp[n - i][k - j] && s[i - 1] != 'X') can_white[i] = true;
        }
    }


    vector<int> can_black(n + 5, 0);

    for(int i = 1; i <= n; ++i) {
        for(int j = 0; j < k; ++j) {
            if(i + c[j] - 1 > n) continue;
            if(query(i - 1, i - 1, black) || query(i + c[j], i + c[j], black)) continue;
            if(query(i, i + c[j] - 1, white)) continue;

            int p = i - 1 - (j != 0);
            if(p < 0) continue;

            if(j == k - 1) {
                if(n - i - c[j] + 1 < 0 || n - i - c[j] + 1 > n) continue;
                if(pref_dp[p][j] && suf_dp[n - i - c[j] + 1][k - j - 1]) {
                    ++can_black[i];
                    --can_black[i + c[j]];
                }
                continue;
            }

            if(n - i - c[j] < 0) continue;
            if(pref_dp[p][j] && suf_dp[n - i - c[j]][k - j - 1]) {
                ++can_black[i];
                --can_black[i + c[j]];
            }
        }
    }

    for(int i = 1; i <= n; ++i) {
        can_black[i] += can_black[i - 1];
    }

    string ans = "";
    for(int i = 1; i <= n; ++i) {
        if(s[i - 1] == '_') {
            ans += '_';
        } else if(s[i - 1] == 'X') {
            ans += 'X';
        } else {
            if(can_black[i] && can_white[i]) {
                ans += '?';
            } else if(can_black[i]) {
                ans += 'X';
            } else ans += '_';
        }
    }
    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