Submission #452117

#	Time	Username	Problem	Language	Result	Execution time	Memory
452117		JovanB	Paint By Numbers (IOI16_paint)	C++17	100 / 100	750 ms	44440 KiB

paint

#include "paint.h"
#include <cstdlib>
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
int whites[200005];
bool white[200005];
int black[200005];
bool dp1[200005][105];
bool dp2[200005][105];
 
int count_white(int l, int r){
    l = max(1, l);
    int x = whites[r] - whites[l-1];
    return x == 0;
}
 
std::string solve_puzzle(std::string s, std::vector<int> c) {
    int k = c.size();
    int n = s.size();
    for(int i=1; i<=n; i++){
        if(s[i-1] == '_') whites[i] = 1;
        whites[i] += whites[i-1];
    }
    dp1[0][0] = 1;
    for(int i=1; i<=n+2; i++){
        dp1[i][0] |= dp1[i-1][0];
        if(i <= n && s[i-1] == 'X') dp1[i][0] = 0;
    }
    dp2[n+2][k+1] = 1;
    for(int i=n+1; i>=0; i--){
        dp2[i][k+1] |= dp2[i+1][k+1];
        if(1 <= i && i <= n && s[i-1] == 'X') dp2[i][k+1] = 0;
    }
    for(int j=1; j<=k; j++){
        for(int i=1; i<=n; i++){
            if(s[i-1] == '_'){
                dp1[i][j] |= dp1[i-1][j];
            }
            else if(s[i-1] == 'X'){
                if(i >= c[j-1] && (i == n || s[i] != 'X') && (i == c[j-1] || s[i-c[j-1]-1] != 'X') && count_white(i-c[j-1]+1, i)){
                    dp1[i][j] |= dp1[max(0, i-c[j-1]-1)][j-1];
                }
            }
            else{
                dp1[i][j] |= dp1[i-1][j];
                if(i >= c[j-1] && (i == n || s[i] != 'X') && (i == c[j-1] || s[i-c[j-1]-1] != 'X') && count_white(i-c[j-1]+1, i)){
                    dp1[i][j] |= dp1[max(0, i-c[j-1]-1)][j-1];
                }
            }
        }
    }
    for(int j=k; j>=1; j--){
        for(int i=n; i>=1; i--){
            if(s[i-1] == '_'){
                dp2[i][j] |= dp2[i+1][j];
            }
            else if(s[i-1] == 'X'){
                if(i+c[j-1]-1 <= n && (i == 1 || s[i-2] != 'X') && (i+c[j-1] == n+1 || s[i+c[j-1]-1] != 'X') && count_white(i, i+c[j-1]-1)){
                    dp2[i][j] |= dp2[i+c[j-1]+1][j+1];
                }
            }
            else{
                dp2[i][j] |= dp2[i+1][j];
                if(i+c[j-1]-1 <= n && (i == 1 || s[i-2] != 'X') && (i+c[j-1] == n+1 || s[i+c[j-1]-1] != 'X') && count_white(i, i+c[j-1]-1)){
                    dp2[i][j] |= dp2[i+c[j-1]+1][j+1];
                }
            }
        }
    }
    for(int i=1; i<=n; i++){
        if(s[i-1] == 'X') continue;
        for(int j=0; j<=k; j++){
            if(dp1[i-1][j] && dp2[i+1][j+1]) white[i] = 1;
        }
    }
    for(int j=1; j<=k; j++){
        for(int i=c[j-1]; i<=n; i++){
            if(count_white(i-c[j-1]+1, i) && (i == c[j-1] || s[i-c[j-1]-1] != 'X') && (i == n || s[i] != 'X') && dp1[max(0, i-c[j-1]-1)][j-1] && dp2[min(n+1, i+2)][j+1]){
                black[i-c[j-1]+1]++;
                black[i+1]--;
            }
        }
    }
    string sol = "";
    int tren = 0;
    for(int i=1; i<=n; i++){
        tren += black[i];
        if(tren && white[i]){
            sol += '?';
        }
        else if(tren){
            sol += 'X';
        }
        else sol += '_';
    }
    return sol;
}

• 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