Submission #232061

#	Time	Username	Problem	Language	Result	Execution time	Memory
232061		DS007	Paint By Numbers (IOI16_paint)	C++14	100 / 100	765 ms	82672 KiB

paint

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

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

    int pw[n] = {}, pb[n] = {}, black[n] = {};
    for (int i = 1; i < n; i++)
        pw[i] = pw[i - 1] + (s[i] == '_'), pb[i] = pb[i - 1] + (s[i] == 'X');

    bool dp1[n][k] = {}, check1[n][k] = {};
    for (int i = c[0]; i < n; i++) {
        dp1[i][0] = pw[i] - pw[i - c[0]] == 0 && pb[i - c[0]] - pb[0] == 0;
        check1[i][0] = s[i] == 'X' ? dp1[i][0] : (dp1[i][0] || check1[i - 1][0]);
        //if (dp1[i][0])
        //    black[i - c[0] + 1] = max(black[i - c[0] + 1], c[0]);
    }

    for (int j = 1; j < k; j++) {
        for (int i = c[j] + 2; i < n; i++) {
            dp1[i][j] = pw[i] - pw[i - c[j]] == 0 && s[i - c[j]] != 'X' && check1[i - c[j] - 1][j - 1];
            check1[i][j] = s[i] == 'X' ? dp1[i][j] : (dp1[i][j] || check1[i - 1][j]);
            //if (dp1[i][j])
            //    black[i - c[j] + 1] = max(black[i - c[j] + 1], c[j]);
        }
    }

    bool dp2[n][k] = {}, check2[n][k] = {};
    for (int i = n - c[k - 1]; i >= 1; i--) {
        dp2[i][k - 1] = pw[i + c[k - 1] - 1] - pw[i - 1] == 0 && pb[n - 1] - pb[i + c[k - 1] - 1] == 0;
        check2[i][k - 1] = s[i] == 'X' ? dp2[i][k - 1] : (dp2[i][k - 1] || check2[i + 1][k - 1]);
        //if (dp2[i][k - 1])
        //    black[i] = max(black[i], c[k - 1]);

    }

    for (int j = k - 2; j >= 0; j--) {
        for (int i = n - c[j] - 2; i >= 1; i--) {
            dp2[i][j] = pw[i + c[j] - 1] - pw[i - 1] == 0 && s[i + c[j]] != 'X' && check2[i + c[j] + 1][j + 1];
            check2[i][j] = s[i] == 'X' ? dp2[i][j] : (dp2[i][j] || check2[i + 1][j]);
            //if (dp2[i][j])
            //    black[i] = max(black[i], c[j]);
        }
    }

    for (int i = 1; i < n; i++) {
        if (dp2[i][0] && pb[i - 1] - pb[0] == 0)
            black[i] = max(black[i], c[0]);
        if (dp1[i][k - 1] && pb[n - 1] - pb[i] == 0)
            black[i - c[k - 1] + 1] = max(black[i - c[k - 1] + 1], c[k - 1]);
    }

    for (int i = 2; i < n; i++) {
        for (int j = 1; j < k; j++)
            if (dp2[i][j] && check1[i - 2][j - 1] && s[i - 1] != 'X')
                black[i] = max(black[i], c[j]);
    }

    bool isBlack[n] = {}, isWhite[n] = {};
    for (int i = 1, j = 0; i < n; i++) {
        for (j = max(j, black[i]); i < n && j; j--, i++, j = max(j, black[i]))
            isBlack[i] = true;
    }

    for (int i = 1; i < n; i++) {
        if (s[i] == 'X')
            continue;

        isWhite[i] = s[i] == '_' || (check1[i - 1][k - 1] && pb[n - 1] - pb[i - 1] == 0) || (i != n - 1 && check2[i + 1][0] && pb[i] - pb[0] == 0);
        for (int j = 0; j < k - 1; j++)
            isWhite[i] = isWhite[i] || (check1[i - 1][j] && (i != n - 1 && check2[i + 1][j + 1]));
    }

    string ans = "";
    for (int i = 1; i < n; i++) {
        assert(isWhite[i] || isBlack[i]);
        if (isWhite[i] && isBlack[i])
            ans += '?';
        else if (isWhite[i])
            ans += '_';
        else if (isBlack[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