Submission #513933

#	Time	Username	Problem	Language	Result	Execution time	Memory
513933		tabr	Paint By Numbers (IOI16_paint)	C++17	59 / 100	2 ms	332 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();
    string res = s;
    {
        vector<vector<int>> a(2, vector<int>(m)), tmp;
        for (int z = 0; z < 2; z++) {
            vector<int> pref(n + 1);
            for (int i = 0; i < n; i++) {
                pref[i + 1] = pref[i] + (s[i] == '_');
            }
            vector<vector<int>> dp(m, vector<int>(n, n));
            for (int i = 0; i < m; i++) {
                int lst = -1;
                for (int j = 0; j + c[i] <= n; j++) {
                    if (j > 0 && s[j - 1] == 'X') {
                        if (i == 0) {
                            break;
                        }
                        lst = j - 1;
                        continue;
                    }
                    if (j + c[i] < n && s[j + c[i]] == 'X') {
                        continue;
                    }
                    if (pref[j] != pref[j + c[i]]) {
                        continue;
                    }
                    if (i == 0) {
                        dp[i][j] = -1;
                    } else {
                        for (int l = 0; l + c[i - 1] < j; l++) {
                            if (dp[i - 1][l] < n && lst < l + c[i - 1]) {
                                dp[i][j] = l;
                                break;
                            }
                        }
                    }
                }
            }
            if (z == 0) {
                tmp = dp;
            }
            int lst = -1;
            for (int i = n - 1; i >= 0; i--) {
                if (s[i] == 'X') {
                    lst = i;
                    break;
                }
            }
            int pos = -1;
            for (int i = 0; i < n; i++) {
                if (dp[m - 1][i] < n && lst < i + c[m - 1]) {
                    pos = i;
                    break;
                }
            }
            for (int i = m - 1; i >= 0; i--) {
                a[z][i] = pos;
                pos = dp[i][pos];
            }
            reverse(s.begin(), s.end());
            reverse(c.begin(), c.end());
        }
        reverse(a[1].begin(), a[1].end());
        for (int i = 0; i < m; i++) {
            a[1][i] = n - 1 - a[1][i];
        }
        vector<int> sum(n + 1);
        for (int i = 0; i < m; i++) {
            for (int j = a[0][i]; j + c[i] - 1 <= a[1][i]; j++) {
                if (tmp[i][j] != n) {
                    sum[j]++;
                    sum[j + c[i]]--;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            sum[i + 1] += sum[i];
            if (s[i] == '.' && sum[i] == 0) {
                res[i] = '_';
            }
        }
    }
    {
        vector dp(2, vector(m + 1, vector<int>(n)));
        for (int z = 0; z < 2; z++) {
            vector<int> pref(n + 1);
            for (int i = 0; i < n; i++) {
                pref[i + 1] = pref[i] + (s[i] == '_');
            }
            for (int i = 0; i < m; i++) {
                int lst = -1;
                for (int j = 0; j + c[i] <= n; j++) {
                    if (j > 0 && s[j - 1] == 'X') {
                        if (i == 0) {
                            break;
                        }
                        lst = j - 1;
                        continue;
                    }
                    if (j + c[i] < n && s[j + c[i]] == 'X') {
                        continue;
                    }
                    if (pref[j] != pref[j + c[i]]) {
                        continue;
                    }
                    if (i == 0) {
                        dp[z][i + 1][j + c[i] - 1] = 1;
                    } else {
                        for (int l = max(0, lst); l + 1 < j; l++) {
                            if (dp[z][i][l]) {
                                dp[z][i + 1][j + c[i] - 1] = 1;
                                break;
                            }
                        }
                    }
                }
            }
            dp[z][0][0] = 1;
            for (int i = 0; i <= m; i++) {
                for (int j = 1; j < n; j++) {
                    if (dp[z][i][j - 1] && s[j] != 'X') {
                        dp[z][i][j] = 1;
                    }
                }
            }
            reverse(s.begin(), s.end());
            reverse(c.begin(), c.end());
        }
        reverse(dp[1].begin(), dp[1].end());
        for (int i = 0; i <= m; i++) {
            reverse(dp[1][i].begin(), dp[1][i].end());
        }
        debug(dp);
        for (int i = 0; i < n; i++) {
            if (res[i] != '.') {
                continue;
            }
            res[i] = 'X';
            if (i == 0) {
                if (n > 1 && dp[1][0][1]) {
                    res[i] = '?';
                }
                continue;
            } else if (i == n - 1) {
                if (n > 1 && dp[0][m][n - 2]) {
                    res[i] = '?';
                }
                break;
            }
            for (int j = 0; j <= m; j++) {
                if (dp[0][j][i - 1] && dp[1][j][i + 1]) {
                    res[i] = '?';
                }
            }
        }
    }
    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}));
    return 0;
}
#endif

• 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