Submission #309681

#	Time	Username	Problem	Language	Result	Execution time	Memory
309681		lohacho	Paint By Numbers (IOI16_paint)	C++14	100 / 100	470 ms	326452 KiB

paint

#include "paint.h"

#include <cstdlib>
#include <bits/stdc++.h>

using namespace std;

using LL = long long;
const int MOD = (int)1e9 + 7;
const int NS = (int)2e5 + 4;
int N, k;
int dpl[NS][104], dpr[NS][104], jump[NS][104];
int jpref[104][NS];
int wpref[NS];
int lw[NS], rw[NS];
string ans;

std::string solve_puzzle(std::string s, std::vector<int> c) {
    N = (int)s.size(), k = (int)c.size();
    s = '?' + s;
    c.push_back(0);
    for(int i = 1; i <= N; ++i){
        lw[i] = lw[i - 1];
        if(s[i] == '_'){
            lw[i] = i;
        }
    }
    rw[N + 1] = N + 1;
    for(int i = N; i >= 1; --i){
        rw[i] = rw[i + 1];
        if(s[i] == '_'){
            rw[i] = i;
        }
    }
    for(int i = k; i >= 1; --i){
        c[i] = c[i - 1];
    }
    for(int i = 1; i <= N; ++i){
        wpref[i] = wpref[i - 1] + (s[i] == '_');
    }
    dpl[0][0] = 1;
    int canzero = 1;
    for(int i = 1; i <= N; ++i){
        if(s[i] == 'X'){
            canzero = 0;
            continue;
        }
        dpl[i][0] = canzero;
        for(int j = 1; j <= k; ++j){
            dpl[i][j] |= dpl[i - 1][j];
            if(i - c[j] - 1 >= 0){
                if(wpref[i - 1] - wpref[i - c[j] - 1]){
                    continue;
                }
                dpl[i][j] |= dpl[i - c[j] - 1][j - 1];
            }
        }
    }
    dpr[N + 1][k + 1] = 1; canzero = 1;
    for(int i = N; i >= 1; --i){
        if(s[i] == 'X'){
            canzero = 0;
            continue;
        }
        dpr[i][k + 1] = canzero;
        for(int j = k; j >= 1; --j){
            dpr[i][j] |= dpr[i + 1][j];
            if(i + c[j] <= N){
                if(wpref[i + c[j]] - wpref[i]){
                    continue;
                }
                dpr[i][j] |= dpr[i + c[j] + 1][j + 1];
            }
        }
    }
    for(int i = 0; i <= N; ++i){
        if(s[i] == 'X'){
            continue;
        }
        for(int j = 1; j <= k; ++j){
            int r = i + c[j] + 1;
            if(r > N + 1){
                continue;
            }
            if(wpref[r - 1] - wpref[i]){
                continue;
            }
            jump[i][j] = (dpl[i][j - 1] & dpr[r][j + 1]);
            if(jump[i][j]){
                ++jpref[j][i];
            }
        }
    }
    for(int i = 1; i <= k; ++i){
        for(int j = 1; j <= N + 1; ++j){
            jpref[i][j] += jpref[i][j - 1];
        }
    }
    for(int i = 1; i <= N; ++i){
        if(s[i] != '.'){
            ans += s[i];
            continue;
        }
        int canw = 0, canb = 0;
        for(int j = 0; j <= k; ++j){
            if(dpl[i][j] & dpr[i][j + 1]){
                canw = 1;
                break;
            }
        }
        if(!canw){
            ans += 'X';
            continue;
        }
        int l_ = lw[i], r_ = rw[i];
        for(int j = 1; j <= k; ++j){
            int posl = max(l_, i - c[j]), posr = min(r_, i + c[j]) - c[j] - 1;
            if(posl > posr){
                continue;
            }
            if(jpref[j][posr] - jpref[j][posl - 1]){
                canb = 1;
                break;
            }
        }
        if(!canb){
            ans += '_';
        }
        else{
            ans += '?';
        }
    }
    return ans;
}

• 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