Submission #598791

#	Time	Username	Problem	Language	Result	Execution time	Memory
598791		jophyyjh	Paint By Numbers (IOI16_paint)	C++14	59 / 100	1 ms	340 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...
 * 
 * Time Complexity: O(nk)
 * Implementation 1
*/

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

typedef std::vector<int>    vec;

template<class T> struct Array2D {
    T* values;
    int _w;
    Array2D(int h, int w)   { values = new T[h * w], _w = w; }
    ~Array2D()              { delete [] values; }
    inline T* operator[](int x)     { return values + x * _w; }
};


std::string solve_puzzle(std::string str, std::vector<int> c) {
    int n = str.size(), seg = c.size();
    vec prefix_b(n + 1), prefix_w(n + 1);      // pre.sum. of black & w
    prefix_b[0] = prefix_w[0] = 0;
    for (int i = 1; i <= n; i++) {
        prefix_b[i] = prefix_b[i - 1] + (str[i - 1] == 'X');
        prefix_w[i] = prefix_w[i - 1] + (str[i - 1] == '_');
    }
    // dp1[i][s] = if it's possible for the first s segments end no later than the
    //             i-th position (but the first s+1 segments do not)
    Array2D<bool> dp1(n + 1, seg + 1), dp2(n + 2, seg + 1);     // fwd & back dir
    dp1[0][0] = dp2[n + 1][0] = 1;
    for (int s = 1; s <= seg; s++)
        dp1[0][s] = 0, dp2[n + 1][s] = 0;
    for (int i = 1; i <= n; i++) {
        for (int s = 0; s <= seg; s++) {
            dp1[i][s] = false;
            dp1[i][s] |= (dp1[i - 1][s] && str[i - 1] != 'X');
            if (s > 0 && i - c[s - 1] - (s > 1) >= 0) {
                dp1[i][s] |= (dp1[i - c[s - 1] - (s > 1)][s - 1]
                                    && prefix_w[i] - prefix_w[i - c[s - 1]] == 0);
            }
        }
    }
    for (int i = n; i >= 1; i--) {
        for (int s = 0; s <= seg; s++) {
            dp2[i][s] = false;
            dp2[i][s] |= (dp2[i + 1][s] && str[i - 1] != 'X');
            if (s > 0 && i + c[seg - s] + (s > 1) <= n + 1) {
                dp2[i][s] |= (dp2[i + c[seg - s] + (s > 1)][s - 1]
                                && prefix_w[i + c[seg - s] - 1] - prefix_w[i - 1] == 0);
            }
        }
    }

    std::vector<bool> can_b(n), can_w(n);
    for (int i = 1; i <= n; i++) {
        can_w[i - 1] = false;
        for (int l = 0; l <= seg && !can_w[i - 1] && str[i - 1] != 'X'; l++)
            can_w[i - 1] = (str[i - 1] != 'X' && dp1[i - 1][l] && dp2[i + 1][seg - l]);
        if (str[i - 1] == '_')
            assert(can_w[i - 1]);
    }
    vec diff(n + 1, 0);     // difference array for black
    for (int i = 0; i < n; i++) {
        for (int s = 0; s < seg; s++) {
            if (i - c[s] + (s == 0) >= 0 && i + 2 + (s < seg - 1) <= n + 1
                  && dp1[i - c[s] + (s == 0)][s] && dp2[i + 2 + (s < seg - 1)][seg - s - 1]
                  && prefix_w[i + 1] - prefix_w[i - c[s] + 1] == 0) {
                bool more_check = true;
                if (s > 0)
                    more_check &= (str[i - c[s]] != 'X');
                if (s < seg - 1)
                    more_check &= (str[i + 1] != 'X');
                if (more_check) {
                    int l = i - c[s] + 1, r = i;
                    diff[l]++, diff[r + 1]--;
                }
            }
        }
    }
    for (int i = 0, prefix_sum = 0; i < n; i++) {
        prefix_sum += diff[i];
        can_b[i] = (prefix_sum > 0);
        assert(str[i] != '_' || !can_b[i]);
        if (str[i] == 'X')
            assert(can_b[i] && !can_w[i]);
    }
    std::string ans;
    for (int i = 0; i < n; i++) {
        assert(can_b[i] || can_w[i]);
        if (can_b[i] && can_w[i])
            ans.push_back('?');
        else if (can_b[i])
            ans.push_back('X');
        else
            ans.push_back('_');
    }
    return ans;
}

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