제출 #159388

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
159388		rama_pang	Paint By Numbers (IOI16_paint)	C++14	90 / 100	2066 ms	26460 KiB

paint

#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma,mmx,tune=native")
#include "paint.h"
#include <bits/stdc++.h>
using namespace std;

string S;
int N, K;
vector<int> C;
vector<int> pref_white, pref_black, lim, ans;
bitset<200000> can_white, can_black;
bitset<200000> memo[100][2], vis[100][2];

inline bool check_white(int le, int ri) { //get number of white spaces in le...ri
    if (ri >= N) return false;
    if (le > ri) return true;
    int res = pref_white[ri];
    if (le > 0) res -= pref_white[le - 1]; 
    return (res == 0);
}

inline bool check_black(int le, int ri) { //get number of black spaces in le...ri
    if (ri >= N) return false;
    if (le > ri) return true;
    int res = pref_black[ri];
    if (le > 0) res -= pref_black[le - 1]; 
    return (res == 0);
}

inline int needed_left(int p) {
    int res = lim[K - 1];
    if (p > 0) res -= lim[p - 1];
    return res;
}

bool dp(int n, int k, int last_black) {
    if (k == K) {
        if (check_black(n, N - 1)) {
            for (int i = n; i < N; i++) can_white[i] = 1;
            return true;
        }
        return false;
    }

    if (n == N) return false;
    if (N - n < needed_left(k)) return false;

    if (vis[k][last_black][n]) return memo[k][last_black][n];
    vis[k][last_black][n] = 1;

    bool res_ = false, resX = false;

    if (S[n] == '_') {
        can_white[n] = 1;
        return memo[k][last_black][n] = dp(n + 1, k, 0);
    } else if (S[n] == 'X') {
        if (!last_black && check_white(n, n + C[k] - 1)) {
            bool res = dp(n + C[k], k + 1, 1);
            if (res) for (int i = n; i < n + C[k]; i++) can_black[i] = 1;
            return memo[k][last_black][n] = res;
        } else {
            return memo[k][last_black][n] = false;
        }
    }

    res_ = dp(n + 1, k, 0);
    if (!last_black && check_white(n, n + C[k] - 1)) resX = dp(n + C[k], k + 1, 1);
    
    if (res_) can_white[n] = 1;
    if (resX) for (int i = n; i < n + C[k]; i++) can_black[i] = 1;

    return memo[k][last_black][n] = (res_ || resX);
}

string solve_puzzle(string s, vector<int> c) {
    S = s;
    N = s.size();
    K = c.size();
    C = c;
    pref_white.resize(N);
    pref_black.resize(N);
    ans.resize(N);
    lim.resize(N);

    // memo.assign(N, vector<vector<bool>>(K, vector<bool>(2, false)));
    // vis.assign(N, vector<vector<bool>>(K, vector<bool>(2, false)));
    
    // memo.assign(K, vector<bitset<200000>>(2));
    // vis.assign(K, vector<bitset<2000000>>(2));
    

    for (int i = 0; i < N; i++) {
        pref_white[i] = (S[i] == '_')? 1 : 0;
        if (i > 0) pref_white[i] += pref_white[i - 1];

        pref_black[i] = (S[i] == 'X')? 1 : 0;
        if (i > 0) pref_black[i] += pref_black[i - 1];
        
        if (S[i] == '.') {
            ans[i] = 0;
        } else if (S[i] == '_') {
            ans[i] = 1;
        } else if (S[i] == 'X') {
            ans[i] = 2;
        }
    }

    for (int i = 0; i < K; i++) {
        lim[i] = C[i];
        if (i > 0) lim[i] += lim[i - 1];
    }

    dp(0, 0, 0);

    string res;
    for (int i = 0; i < N; i++) {
        ans[i] = can_white[i] | (can_black[i] << 1);
        if (ans[i] == 0) {
            res.push_back('E');
        } else if (ans[i] == 1) {
            res.push_back('_');
        } else if (ans[i] == 2) {
            res.push_back('X');
        } else {
            res.push_back('?');
        }
    }

    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: 0 / 10