Submission #562864

#	Time	Username	Problem	Language	Result	Execution time	Memory
562864		elazarkoren	Paint By Numbers (IOI16_paint)	C++17	59 / 100	2 ms	232 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const int MAX_N = 5005;
const int MAX_K = 105;

bool dp[MAX_N][MAX_K];
int n, k;
int next_bad[MAX_N];

bool Check(string &s, vi &c, int start) {
    for (int i = start; i < n; i++) {
        for (int j = 0; j < k; j++) {
            dp[i][j] = false;
        }
    }
    int ex = n;
    next_bad[n] = n;
    for (int i = n - 1; i >= 0; i--) {
        next_bad[i] = next_bad[i + 1];
        if (s[i] == 'X') ex = i;
        else if (s[i] == '_') next_bad[i] = i;
    }
    for (int i = start; i < n; i++) {
        if (s[i] != 'X') {
            if (i) {
                for (int j = 0; j < k; j++) {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        if (s[i] == '_') continue;
        for (int j = 0, sum = -1; j < k; j++) {
            sum += c[j] + 1;
            if (sum > i + 1) break;
            bool b = i - c[j] + 1 < 0 || next_bad[i - c[j] + 1] > i;
            if (b && !j) {
                dp[i][j] |= ex > i - c[j];
            } else if (b && (i - c[j] < 0 || s[i - c[j]] != 'X') && (i - c[j] <= 0 || dp[i - c[j] - 1][j - 1])) {
                dp[i][j] = true;
            }
        }
    }
    return dp[n - 1][k - 1];
}

std::string solve_puzzle(std::string s, std::vector<int> c) {
    n = s.size();
    k = c.size();
    string ans(n, '?');
    int ex = n;
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == 'X') ex = i;
    }
    for (int i = 0; i < n; i++) {
        if (s[i] != '.') ans[i] = s[i];
        else {
            s[i] = '_';
            bool b1 = Check(s, c, i);
            s[i] = 'X';
            bool b2 = Check(s, c, i);
            s[i] = '.';
            if (b1 && !b2) ans[i] = s[i] = '_';
            else if (!b1 && b2) ans[i] = s[i] = 'X';
        }
        if (s[i] != 'X') {
            for (int j = 0; j < k; j++) {
                dp[i][j] = i ? dp[i - 1][j] : false;
            }
        }
        if (s[i] == '_') continue;
        for (int j = 0, sum = -1; j < k; j++) {
            sum += c[j] + 1;
            if (sum > i + 1) break;
            bool b = i - c[j] + 1 < 0 || next_bad[i - c[j] + 1] > i;
            if (b && !j) {
                dp[i][j] |= ex > i - c[j];
            } else if (b && (i - c[j] < 0 || s[i - c[j]] != 'X') && (i - c[j] <= 0 || dp[i - c[j] - 1][j - 1])) {
                dp[i][j] = true;
            }
        }
    }
    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