Submission #598845

#	Time	Username	Problem	Language	Result	Execution time	Memory
598845		jophyyjh	Paint By Numbers (IOI16_paint)	C++14	100 / 100	405 ms	82104 KiB

paint

/**
 * Nice little problem. O(nk) may work, so let's just do dp. Well, this problem
 * mainly tests a contestant's fundamentals, e.g. things like prefix sum, dp,
 * difference array, etc. Really tedious to code...
 * If i met such problem in the real contest, i definitely cannot AC it. It just took
 * me too long to code...
 * 
 * Well, after coding for a while, i noticed that my impl1 is indeed too tedious. I
 * then switched my way of coding (in impl2) by adding a third column in dp. This
 * makes my solution much cleaner.
 * 
 * Time Complexity: O(nk)
 * Implementation 2     (re-coded everything)
*/

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

typedef std::vector<int>    vec;

const int N_MAX = 2 * 1e5;
const int SEG_MAX = 100;


// dpX[i][s][b] = whether it's possible for the first s segments to sit completely
//                before (or at) the i-th pos, with the i-th position being b
//                b: 0 for W, 1 for B
bool dp1[N_MAX + 1][SEG_MAX + 1][2];    // fwd dir
bool dp2[N_MAX + 2][SEG_MAX + 1][2];    // back dir

std::string solve_puzzle(std::string str, std::vector<int> c) {
    int n = str.length(), seg = c.size();
    std::vector<int> prefix_w(n + 1);
    prefix_w[0] = 0;
    for (int k = 0; k < n; k++)
        prefix_w[k + 1] = prefix_w[k] + (str[k] == '_');

    dp1[0][0][0] = dp2[n + 1][0][0] = 1;
    dp1[0][0][1] = dp2[n + 1][0][1] = 0;
    for (int s = 1; s <= seg; s++) {
        for (int b = 0; b < 2; b++)
            dp1[0][s][b] = dp2[n + 1][s][b] = 0;
    }
    for (int i = 1; i <= n; i++) {
        for (int s = 0; s <= seg; s++) {
            dp1[i][s][0] = ((dp1[i - 1][s][0] || dp1[i - 1][s][1]) && str[i - 1] != 'X');
            dp1[i][s][1] = false;
            if (s > 0 && i - c[s - 1] >= 0 && prefix_w[i] - prefix_w[i - c[s - 1]] == 0)
                dp1[i][s][1] |= dp1[i - c[s - 1]][s - 1][0];
        }
    }
    for (int i = n; i >= 1; i--) {
        for (int s = 0; s <= seg; s++) {
            dp2[i][s][0] = ((dp2[i + 1][s][0] || dp2[i + 1][s][1]) && str[i - 1] != 'X');
            dp2[i][s][1] = false;
            if (s > 0 && i + c[seg - s] <= n + 1 && prefix_w[i + c[seg - s] - 1] - prefix_w[i - 1] == 0)
                dp2[i][s][1] |= dp2[i + c[seg - s]][s - 1][0];
        }
    }

    std::vector<bool> can_w(n), can_b(n);
    for (int i = 1; i <= n; i++) {
        can_w[i - 1] = false;
        for (int l = 0; l <= seg && !can_w[i - 1]; l++) {
            can_w[i - 1] = (str[i - 1] != 'X'
                                && (dp1[i - 1][l][0] || dp1[i - 1][l][1])
                                && (dp2[i + 1][seg - l][0] || dp2[i + 1][seg - l][1]));
        }
    }
    std::vector<int> diff(n + 1, 0);    // difference array
    for (int k = 0; k < seg; k++) {
        for (int l = 1; l <= n; l++) {
            int r = l + c[k] - 1;
            if (r > n)
                break;
            if (prefix_w[r] - prefix_w[l - 1] == 0
                    && dp1[l - 1][k][0] && dp2[r + 1][seg - k - 1][0]) {
                diff[l - 1]++, diff[r]--;
            }
        }
    }
    for (int i = 0, prefix_sum = 0; i < n; i++) {
        prefix_sum += diff[i];
        can_b[i] = (prefix_sum > 0);
    }

    std::string ans;
    for (int k = 0; k < n; k++) {
        char status;
        assert(can_b[k] || can_w[k]);
        if (can_b[k] && can_w[k])
            status = '?';
        else if (can_b[k])
            status = 'X';
        else
            status = '_';
        if (str[k] != '.')
            assert(str[k] == status);
        ans.push_back(status);
    }
    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