Submission #514177

#	Time	Username	Problem	Language	Result	Execution time	Memory
514177		tabr	Paint By Numbers (IOI16_paint)	C++17	100 / 100	513 ms	163756 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();
    s = "X_" + s + "_X";
    c.insert(c.begin(), 1);
    c.emplace_back(1);
    n += 4;
    m += 2;
    vector<int> pref(n + 1);
    for (int i = 0; i < n; i++) {
        pref[i + 1] = pref[i] + (s[i] == '_');
    }
    vector<vector<int>> left(m, vector<int>(n));
    left[0][0] = 1;
    for (int i = 0; i < m; i++) {
        if (i != 0) {
            for (int j = 1; j + c[i] - 1 < n; j++) {
                if (s[j - 1] != 'X' && (j + c[i] == n || s[j + c[i]] != 'X') && pref[j] == pref[j + c[i]]) {
                    left[i][j + c[i] - 1] |= left[i - 1][j - 2];
                }
            }
        }
        for (int j = 1; j < n; j++) {
            if (s[j] != 'X') {
                left[i][j] |= left[i][j - 1];
            }
        }
    }
    vector<vector<int>> right(m, vector<int>(n));
    right[m - 1][n - 1] = 1;
    for (int i = m - 1; i >= 0; i--) {
        if (i != m - 1) {
            for (int j = n - 2; j - c[i] + 1 >= 0; j--) {
                if (s[j + 1] != 'X' && (j - c[i] == -1 || s[j - c[i]] != 'X') && pref[j - c[i] + 1] == pref[j + 1]) {
                    right[i][j - c[i] + 1] |= right[i + 1][j + 2];
                }
            }
        }
        for (int j = n - 2; j >= 0; j--) {
            if (s[j] != 'X') {
                right[i][j] |= right[i][j + 1];
            }
        }
    }
    vector<int> black(n + 1);
    vector<int> white(n + 1);
    for (int i = 1; i < m; i++) {
        for (int j = 2; j < n - 2; j++) {
            if (left[i - 1][j - 1] && right[i][j + 1] && s[j] != 'X') {
                white[j] = 1;
            }
        }
    }
    for (int i = 1; i < m - 1; i++) {
        for (int j = 2; j + c[i] <= n - 2; j++) {
            if (s[j - 1] == 'X' || s[j + c[i]] == 'X' || pref[j] != pref[j + c[i]]) {
                continue;
            }
            if (left[i - 1][j - 2] && right[i + 1][j + c[i] + 1]) {
                black[j]++;
                black[j + c[i]]--;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        black[i + 1] += black[i];
    }
    string res;
    for (int i = 2; i < n - 2; i++) {
        if (black[i] && white[i]) {
            res += "?";
        } else if (black[i]) {
            res += "X";
        } else if (white[i]) {
            res += "_";
        } else {
            res += "!";
        }
    }
    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}));
    debug(solve_puzzle(".X.._.......", {1, 2, 3}));
    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: 10 / 10
• Subtask 7: 10 / 10