제출 #562876

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
562876		elazarkoren	Paint By Numbers (IOI16_paint)	C++17	32 / 100	2 ms	268 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;

bitset<MAX_K> dp[MAX_N];
bitset<MAX_K> dpr[MAX_N];
int n, k;
int next_bad[MAX_N];

bool Check(string &s, vi &c, int start) {
    for (int i = start; i < n; i++) {
        dp[i].reset();
    }
    int ex = 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' && i) {
            dp[i] = dp[i - 1];
        }
        if (s[i] == '_') continue;
        for (int j = 0, sum = -1; j < k; j++) {
            sum += c[j] + 1;
            if (dp[i][j]) continue;
            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];
}

bitset<MAX_N> check_;

std::string solve_puzzle(std::string s, std::vector<int> c) {
    n = s.size();
    k = c.size();
    string ans(n, '?');

    int ex = 0;
    next_bad[0] = s[0] == 'X' ? 0 : -1;
    for (int i = 0; i < n; i++) {
        next_bad[i] = next_bad[i + 1];
        if (s[i] == 'X') ex = i;
        else if (s[i] == '_') next_bad[i] = i;
    }
    dpr[n][k] = true;
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] != 'X') {
            dpr[i] = dpr[i + 1];
        }
        if (s[i] == '_') continue;
        for (int j = k - 1, sum = -1; j >= 0; j--) {
            sum += c[j] + 1;
            if (dpr[i][j]) continue;
            if (sum > n - i) break;
            bool b = next_bad[i + c[j] - 1] < i;
            if (b && j == k) {
                dpr[i][j] = ex < i + c[j];
            } else if (b && (i + c[j] >= n || s[i + c[j]] != 'X') && (i + c[j] + 1 >= n || dpr[i + c[j] + 1][j + 1])) {
                dpr[i][j] = true;
            }
        }
    }

    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 = 0; i < n; i++) {
        if (s[i] != 'X' && i) {
            dp[i] = dp[i - 1];
        }
        if (s[i] == '_') continue;
        for (int j = 0, sum = -1; j < k; j++) {
            sum += c[j] + 1;
            if (dp[i][j]) continue;
            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;
            }
        }
    }
    if (dpr[1][0]) check_[0] = true;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < k; j++) {
            if (dp[i - 1][j] && dpr[i + 1][j + 1]) {
                check_[i] = true;
                break;
            }
        }
        if (dpr[i + 1][0] && ex > i) check_[i] = true;
    }
    for (int i = 0; i < n; i++) {
        if (s[i] != '.') ans[i] = s[i];
        else {
            s[i] = 'X';
            bool b2 = Check(s, c, 0);
            s[i] = '.';
            if (check_[i] && !b2) ans[i] = s[i] = '_';
            else if (!check_[i] && b2) {
                ans[i] = s[i] = 'X';
                chkmin(ex, i);
            }
        }
        for (int j = n - 1; j >= 0; j--) {
            next_bad[j] = next_bad[j + 1];
            if (s[j] == 'X') ex = j;
            else if (s[j] == '_') next_bad[j] = j;
        }
        dp[i].reset();
        if (s[i] != 'X' && i) {
            dp[i] = dp[i - 1];
        }
        if (s[i] == '_') continue;
        for (int j = 0, sum = -1; j < k; j++) {
            sum += c[j] + 1;
            if (dp[i][j]) continue;
            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: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10