Submission #1059416

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059416		ArthuroWich	Paint By Numbers (IOI16_paint)	C++17	100 / 100	289 ms	176080 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
string solve_puzzle(string s, vector<int> c) {
    int n = s.length(), k = c.size();
    s = "@"+s+"@";
    vector<int> pref(n+2, 0);
    vector<vector<int>> dpl(n+2, vector<int>(k+1, 0)), dpr(n+2, vector<int>(k+1, 0));
    for (int i = 1; i <= n+1; i++) {
        pref[i] = pref[i-1];
        if (s[i] == '_') {
            pref[i]++;
        }
    }
    dpl[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            if (s[i] != 'X') {
                dpl[i][j] |= dpl[i-1][j];
            }
            if (j > 0 && i-c[j-1] >= 0 && pref[i]-pref[i-c[j-1]] == 0 && (i-c[j-1] <= 0 || s[i-c[j-1]] != 'X')) {
                dpl[i][j] |= dpl[max(0, i-c[j-1]-1)][j-1];
            }
        }
    }
    reverse(c.begin(), c.end());
    dpr[n+1][0] = 1;
    for (int i = n; i >= 1; i--) {
        for (int j = 0; j <= k; j++) {
            if (s[i] != 'X') {
                dpr[i][j] |= dpr[i+1][j];
            }
            if (j > 0 && i+c[j-1] <= n+1 && pref[i+c[j-1]-1]-pref[i-1] == 0 && (i+c[j-1] > n || s[i+c[j-1]] != 'X')) {
                dpr[i][j] |= dpr[min(n+1, i+c[j-1]+1)][j-1];
            }
        }
    }
    //for (int i = 1; i < n+2; i++) {
    //    for (int j = 0; j <= k; j++) {
    //        cout << dpl[i][j] << " ";
    //    }
    //    cout << endl;
    //}
    //cout << endl;
    //for (int i = 1; i < n+2; i++) {
    //    for (int j = 0; j <= k; j++) {
    //        cout << dpr[i][j] << " ";
    //    }
    //    cout << endl;
    //}
    vector<pair<int, int>> ans(n+2, {0, 0});
    for (int i = 1; i <= n; i++) {
        if (s[i] == 'X') {
            continue;
        }
        for (int j = 0; j <= k; j++) {
            int kr = k-j;
            if (dpl[i-1][j] && dpr[i+1][kr]) {
                ans[i].first = 1;
            }
        }
    }
    reverse(c.begin(), c.end());
    for (int i = 1; i <= n; i++) {
        if (s[i] == '_') {
            continue;
        }
        for (int j = 0; j <= k; j++) {
            int kr = k-j;
            if (!dpr[min(n+1, i+2)][kr] || (i+1 <= n && s[i+1] == 'X')) {
                continue;
            }
            if (j > 0 && i-c[j-1] >= 0 && pref[i]-pref[i-c[j-1]] == 0 && (i-c[j-1] <= 0 || s[i-c[j-1]] != 'X') && dpl[max(0, i-c[j-1]-1)][j-1]) {
                for (int l = i-c[j-1]+1; l <= i; l++) {
                    ans[l].second = 1;
                }
            }
        }
    }
    reverse(c.begin(), c.end());
    for (int i = n; i >= 1; i--) {
        if (s[i] == '_') {
            continue;
        }
        for (int j = 0; j <= k; j++) {
            int kl = k-j;
            if (!dpl[max(0, i-2)][kl] || (i-1 >= 1 && s[i-1] == 'X')) {
                continue;
            }
            if (j > 0 && i+c[j-1] <= n+1 && pref[i+c[j-1]-1]-pref[i-1] == 0 && (i+c[j-1] > n || s[i+c[j-1]] != 'X') && dpr[min(n+1, i+c[j-1]+1)][j-1]) {
                for (int l = i; l <= i+c[j-1]-1; l++) {
                    ans[l].second = 1;
                }
            }
        }
    }
    string res = "";
    for (int i = 1; i <= n; i++) {
        if (ans[i].first && ans[i].second) {
            res.push_back('?');
        } else if (ans[i].first) {
            res.push_back('_');
        } else if (ans[i].second) {
            res.push_back('X');
        } else {
            res.push_back('B');
        }
    }
    return res;
}

• 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