Submission #426401

#	Time	Username	Problem	Language	Result	Execution time	Memory
426401		timmyfeng	Paint By Numbers (IOI16_paint)	C++17	100 / 100	488 ms	82376 KiB

paint

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

const int N = 200001, K = 101;

bool prefix[N][K][2], suffix[N][K][2], white[N];
int black[N], sum[N], n, k;

void solve(bool possible[N][K][2], string s, vector<int> c) {
    for (int i = 0; i < n; ++i) {
        sum[i + 1] = sum[i] + (s[i] == '_');
    }

    possible[0][0][0] = true;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= k; ++j) {
            possible[i + 1][j][0] |= s[i] != 'X' && (possible[i][j][0] || possible[i][j][1]);
            if (j < k && i + c[j] <= n) {
                possible[i + c[j]][j + 1][1] |= sum[i + c[j]] == sum[i] && possible[i][j][0];
            }
        }
    }
}

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

    reverse(s.begin(), s.end());
    reverse(c.begin(), c.end());
    solve(suffix, s, c);

    reverse(s.begin(), s.end());
    reverse(c.begin(), c.end());
    solve(prefix, s, c);

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= k; ++j) {
            if (prefix[i][j][0] && (suffix[n - i][k - j][0] || suffix[n - i][k - j][1])) {
                white[i - 1] = true;
            }
            if (prefix[i][j][1] && suffix[n - i][k - j][0]) {
                ++black[i - c[j - 1]], --black[i];
            }
        }
    }
    partial_sum(black, black + n, black);

    string ans;
    for (int i = 0; i < n; ++i) {
        if (white[i] && black[i] == 0) {
            ans += '_';
        } else if (black[i] > 0 && !white[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