Submission #513969

#	Time	Username	Problem	Language	Result	Execution time	Memory
513969		tabr	Paint By Numbers (IOI16_paint)	C++17	80 / 100	2005 ms	2324 KiB

paint

#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

string solve_puzzle(string s, vector<int> c) {
    int n = (int) s.size();
    int m = (int) c.size();
    string res = s;
    auto check = [&]() {
        vector<vector<int>> dp(m, vector<int>(n));
        vector<vector<int>> sum(m, vector<int>(n + 1));
        vector<int> pref(n + 1);
        for (int i = 0; i < n; i++) {
            pref[i + 1] = pref[i] + (s[i] == '_');
        }
        for (int i = 0; i < m; i++) {
            int lst = -1;
            for (int j = 0; j + c[i] <= n; j++) {
                sum[i][j + c[i]] = sum[i][j + c[i] - 1];
                if (j > 0 && s[j - 1] == 'X') {
                    if (i == 0) {
                        for (int k = j + c[i] + 1; k <= n; k++) {
                            sum[i][k] = sum[i][k - 1];
                        }
                        break;
                    }
                    lst = j - 1;
                    continue;
                }
                if (j + c[i] < n && s[j + c[i]] == 'X') {
                    continue;
                }
                if (pref[j] != pref[j + c[i]]) {
                    continue;
                }
                if (i == 0) {
                    dp[i][j + c[i] - 1] = 1;
                } else {
                    if (j > 1 && sum[i - 1][max(0, lst)] != sum[i - 1][j - 1]) {
                        dp[i][j + c[i] - 1] = 1;
                    }
                }
                sum[i][j + c[i]] += dp[i][j + c[i] - 1];
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            if (dp[m - 1][i]) {
                return 1;
            }
            if (s[i] == 'X') {
                break;
            }
        }
        return 0;
    };
    for (int i = 0; i < n; i++) {
        if (s[i] != '.') {
            continue;
        }
        s[i] = 'X';
        int x = check();
        s[i] = '_';
        int y = check();
        s[i] = '.';
        if (!x) {
            res[i] = '_';
        } else if (!y) {
            res[i] = 'X';
        } else {
            res[i] = '?';
        }
    }
    return res;
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    debug(solve_puzzle("..........", {3, 4}));
    debug(solve_puzzle("........", {3, 4}));
    debug(solve_puzzle("..._._....", {3}));
    debug(solve_puzzle(".X........", {3}));
    debug(solve_puzzle("....X..X...", {3, 3}));
    debug(solve_puzzle("..X_.._X...", {1, 2, 1}));
    debug(solve_puzzle(".._.X_.._.._X.", {2, 2, 2}));
    debug(solve_puzzle("..X_.._X....", {1, 2, 2}));
    return 0;
}
#endif

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