Submission #370029

#	Time	Username	Problem	Language	Result	Execution time	Memory
370029		KoD	Paint By Numbers (IOI16_paint)	C++17	100 / 100	957 ms	56356 KiB

paint

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

template <class T>
using Vec = std::vector<T>;
using String = std::string;

Vec<Vec<char>> precompute(const String &s, const Vec<int> &c) {
    const int n = (int) s.size();
    const int k = (int) c.size();
    Vec<int> count(n + 1);
    for (int i = 0; i < n; ++i) {
        count[i + 1] = count[i] + (s[i] == '_');
    }
    Vec<Vec<char>> dp(n + 1, Vec<char>(k + 1));
    dp[0][0] = true;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= k; ++j) {
            if (!dp[i][j]) {
                continue;
            }
            if (s[i] != 'X') {
                dp[i + 1][j] = true;
                if (j != k) {
                    const int l = i + 1;
                    const int r = l + c[j];
                    if (r <= n && count[r] - count[l] == 0) {
                        dp[r][j + 1] = true;
                    }
                }
            }
            if (j == 0) {
                const int l = i;
                const int r = l + c[j];
                if (r <= n && count[r] - count[l] == 0) {
                    dp[r][j + 1] = true;
                }
            }
        }
    }
    return dp;
}

String solve_puzzle(String s, Vec<int> c) {
    const int n = (int) s.size();
    const int k = (int) c.size();
    const auto left = precompute(s, c);
    const auto right = precompute(String(s.rbegin(), s.rend()), Vec<int>(c.rbegin(), c.rend()));
    Vec<char> white(n);
    for (int i = 0; i < n; ++i) {
        if (s[i] != 'X') {
            for (int j = 0; j <= k; ++j) {
                if (left[i][j] && right[n - i - 1][k - j]) {
                    white[i] = true;
                    break;
                }
            }
        }
    }
    Vec<int> count(n + 1);
    for (int i = 0; i < n; ++i) {
        count[i + 1] = count[i] + (s[i] == '_');
    }
    Vec<int> black(n + 1);
    for (int j = 0; j < k; ++j) {
        for (int l = 0; l < n; ++l) {
            const int r = l + c[j];
            if (r > n) {
                break;
            }
            const bool left_ok = [&] {
                if (l == 0) return j == 0;
                return s[l - 1] != 'X' && left[l - 1][j];
            }();
            const bool right_ok = [&] {
                if (r == n) return j + 1 == k;
                return s[r] != 'X' && right[n - r - 1][k - j - 1];
            }();
            if (left_ok && right_ok && count[r] - count[l] == 0) {
                black[l] += 1;
                black[r] -= 1;
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        black[i + 1] += black[i];
    }
    String ret(n, '?');
    for (int i = 0; i < n; ++i) {
        if (!white[i]) {
            ret[i] = 'X';
        }
        if (!black[i]) {
            ret[i] = '_';
        }
    }
    return ret;
}

• 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