제출 #254298

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
254298		Hehehe	Paint By Numbers (IOI16_paint)	C++14	100 / 100	823 ms	90040 KiB

paint

#include<bits/stdc++.h> //:3
using namespace std;
typedef long long ll;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define rc(s) return cout<<s,0
#define pi pair <int, int>
#define sz(x) (int)((x).size())

#include "paint.h"

const int K = 110;
const int N = 200010;

bool pref[N][K][2], suf[N][K][2];
int w[N], canW[N], canB[N];

string solve_puzzle(string s, vector<int> c){

    int n = sz(s);
    s = '.' + s;

    int k = sz(c);

    vector<int>v;
    v.push_back(0);

    for(auto it : c)v.push_back(it);

    for(int i = 1; i <= n; i++){
        w[i] = w[i - 1] + (s[i] == '_');
    }

    pref[0][0][0] = pref[0][0][1] = 1;
    suf[n + 1][k  + 1][0] = suf[n + 1][k + 1][1] = 1;

    //prefix
    for(int j = 0; j <= k; j++){
        for(int i = 1; i <= n; i++){

            if(s[i] == '_' || s[i] == '.'){
                pref[i][j][0] = pref[i - 1][j][1];
                pref[i][j][1] = pref[i - 1][j][1];
            }

            if(j == 0 || i - v[j] < 0 || (w[i] - w[i - v[j]]) != 0) continue;

            if(s[i] == 'X' || s[i] == '.'){
                pref[i][j][1] = pref[i][j][1] || pref[i - v[j]][j - 1][0];
            }
        }
    }

    //sufix
    for(int j = k + 1; j >= 1; j--){
        for(int i = n; i >= 1; i--){

            if(s[i] == '_' || s[i] == '.'){
                suf[i][j][0] = suf[i + 1][j][1];
                suf[i][j][1] = suf[i + 1][j][1];
            }

            if(j == k + 1 || i + v[j] - 1 > n || (w[i + v[j] - 1] - w[i - 1]) != 0) continue;

            if(s[i] == 'X' || s[i] == '.'){
                suf[i][j][1] = suf[i][j][1] || suf[i + v[j]][j + 1][0];
            }
        }
    }

    //which positions can be white
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= k; j++){
            if(pref[i - 1][j][1] && suf[i + 1][j + 1][1])canW[i] = 1;
        }
    }

    //which positions can be black #BlackPositionsMatter
    for(int j = 1; j <= k; j++){

        for(int r = 1; r <= n; r++){

            int l = r - v[j] + 1;

            if(l <= 0 || w[r] - w[l - 1] != 0)continue;

            if(pref[l - 1][j - 1][0] && suf[r + 1][j + 1][0]){
                canB[l]++;
                canB[r + 1]--;
            }

        }
    }

    for(int i = 1; i <= n; i++){
        canB[i] += canB[i - 1];
    }

    string ans = "";

    for(int i = 1; i <= n; i++){

        if(s[i] != '.'){
            ans += s[i];
            continue;
        }

        if(canW[i] && canB[i])ans += '?';else
        if(canW[i])ans += '_';else ans += 'X';
    }

    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