Submission #592999

#	Time	Username	Problem	Language	Result	Execution time	Memory
592999		skittles1412	Paint By Numbers (IOI16_paint)	C++17	100 / 100	947 ms	188356 KiB

paint

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__);
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

using vvc = vector<vector<char>>;

struct Psum {
    int n;
    vector<int> psum;

    Psum(const vector<int>& arr) : n(sz(arr)), psum(n + 1) {
        partial_sum(begin(arr), end(arr), psum.begin() + 1);
    }

    int query(int l, int r) const {
        return psum[r + 1] - psum[l];
    }
};

struct Rsum {
    vector<int> psum;

    Rsum(int n) : psum(n + 1) {}

    void add(int l, int r) {
        psum[l]++;
        psum[r + 1]--;
    }

    vector<int> query() {
        vector<int> tmp(sz(psum));
        partial_sum(begin(psum), end(psum), tmp.begin());
        return tmp;
    }
};

Psum pseq(const string& s, char c) {
    vector<int> tmp(sz(s));
    for (int i = 0; i < sz(s); i++) {
        tmp[i] = s[i] == c;
    }
    return Psum(tmp);
}

pair<vvc, vvc> solve(const string& s, const vector<int>& arr) {
    int n = sz(s), m = sz(arr);
    Psum whites = pseq(s, '_');
    vvc dp(n + 1, vector<char>(m + 1)), start(n + 1, vector<char>(m + 1)),
        xstart(n + 1, vector<char>(m + 1));
    dp[n][m] = start[n][m] = xstart[n][m] = true;
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] != 'X') {
            dp[i][m] = start[i][m] = xstart[i][m] = dp[i + 1][m];
        }
        for (int j = 0; j < m; j++) {
            if (i + arr[j] <= n && !whites.query(i, i + arr[j] - 1)) {
                dp[i][j] = start[i][j] = xstart[i + arr[j]][j + 1];
            }
            if (s[i] != 'X') {
                xstart[i][j] = dp[i + 1][j];
                dp[i][j] |= dp[i + 1][j];
            }
        }
    }
    return {dp, start};
}

template <typename T>
T reversed(T x) {
    reverse(begin(x), end(x));
    return x;
}

string solve_puzzle(string s, vector<int> arr) {
    int n = sz(s), m = sz(arr);
    auto [suff, sufx] = solve(s, arr);
    auto [pref, _] = solve(reversed(s), reversed(arr));
    Rsum cblack(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            bool pa;
            if (!i) {
                pa = !j;
            } else {
                pa = s[i - 1] != 'X' && pref[n - i + 1][m - j];
            }
            if (pa && sufx[i][j]) {
                dbg(i, j, i + arr[j] - 1);
                cblack.add(i, i + arr[j] - 1);
            }
        }
    }
    auto qblack = cblack.query();
    string ans;
    for (int i = 0; i < n; i++) {
        bool white = false;
        for (int j = 0; j <= m; j++) {
            white |= s[i] != 'X' && pref[n - i][m - j] && suff[i + 1][j];
        }
        bool black = !!qblack[i];
        dbg(i, white, black);
        if (white && !black) {
            ans.push_back('_');
        } else if (black && !white) {
            ans.push_back('X');
        } else if (black && white) {
            ans.push_back('?');
        } else {
            assert(false);
        }
    }
    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