Submission #593061

#	Time	Username	Problem	Language	Result	Execution time	Memory
593061		FatihSolak	Paint By Numbers (IOI16_paint)	C++17	100 / 100	359 ms	44912 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#define N 200005
#define K 105
using namespace std;
int prew[N];
int preb[N];
bool predp[N][K];
bool sufdp[N][K];
int canb[N];
int cntw(int l,int r){
    return prew[r] - prew[l-1];
}
int cntb(int l,int r){
    return preb[r] - preb[l-1];
}
string solve_puzzle(string s, vector<int> c) {
    for(auto &u:s)if(u == '.')u = '?';
    s = "#" + s + "_";
    int n = s.size() - 1;
    int k = c.size();
    for(int i = 1;i<=n;i++){
        prew[i] = prew[i-1] + (s[i] == '_');
        preb[i] = preb[i-1] + (s[i] == 'X');
    }
    predp[0][0] = 1;
    for(int i = 1;i<=n;i++){
        for(int j = 0;j<=k;j++){
            if(s[i] != 'X'){
                predp[i][j] |= predp[i-1][j];
            }
        }
        for(int j = 1;j<=k;j++){
            if(i + c[j-1] <= n && cntw(i,i+c[j-1]-1) == 0 && cntb(i+c[j-1],i+c[j-1]) == 0){
                predp[i+c[j-1]][j] |= predp[i-1][j-1];
            }
        }
    }
    sufdp[n+1][k+1] = 1;
    for(int i = n;i>=1;i--){
        for(int j = 1;j<=k+1;j++){
            if(s[i] != 'X'){
                sufdp[i][j] |= sufdp[i+1][j];
            }
        }
        for(int j = 1;j<=k;j++){
            if(i - c[j-1] >= 1 && cntw(i-c[j-1],i-1) == 0 && cntb(i,i) == 0){
                sufdp[i-c[j-1]][j] |= sufdp[i+1][j+1];
            }
        }
    }
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=k;j++){
            if(i + c[j-1] <= n && cntw(i,i+c[j-1]-1) == 0 && cntb(i+c[j-1],i+c[j-1]) == 0 && predp[i-1][j-1] && sufdp[i+c[j-1]+1][j+1]){
                canb[i] += 1;
                canb[i + c[j-1]] -= 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;
        }
        bool canw = 0;
        for(int j = 0;j<=k;j++){
            canw |= predp[i][j] && sufdp[i+1][j+1];
        }
        if(canb[i] && canw)ans += "?";
        else if(canb[i])ans += "X";
        else if(canw)ans += '_';
        else assert(0);
    }
    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