Submission #30490

#	Time	Username	Problem	Language	Result	Execution time	Memory
30490		zoomswk	Paint By Numbers (IOI16_paint)	C++14	100 / 100	973 ms	169784 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;

char ss[200015];
int cc[200015];
int dp[200015][105];
int dp_rev[200015][105];
int ok_white[200015];
int ok_black[200015];

std::string solve_puzzle(std::string s, std::vector<int> c) {
    int n = s.length(), k = c.size();
    for(int i=2; i<=n+1; i++) ss[i] = s[i-2];
    for(int i=1; i<=k; i++) cc[i] = c[i-1];

    dp[0][0] = 1;
    dp[1][0] = 1;

    int black_able = 0;
    for(int i=2; i<=n+1; i++){
        if(ss[i] != '_') black_able++;
        else black_able = 0;
        if(ss[i] != 'X') for(int j=0; j<=k; j++) dp[i][j] = dp[i-1][j];
        for(int j=1; j<=k; j++){
            if(cc[j] > black_able) continue;
            if(ss[i-cc[j]] == 'X') continue;
            dp[i][j] |= dp[i-cc[j]-1][j-1];
        }
    }

    /*
    for(int i=2; i<=n+1; i++){
        for(int j=0; j<=k; j++) printf("%d ", dp[i][j]);
        printf("\n");
    }
    */

    dp_rev[n+3][k+1] = 1;
    dp_rev[n+2][k+1] = 1;

    black_able = 0;
    for(int i=n+1; i>=2; i--){
        if(ss[i] != '_') black_able++;
        else black_able = 0;
        if(ss[i] != 'X') for(int j=1; j<=k+1; j++) dp_rev[i][j] = dp_rev[i+1][j];
        for(int j=1; j<=k; j++){
            if(cc[j] > black_able) continue;
            if(ss[i+cc[j]] == 'X') continue;
            dp_rev[i][j] |= dp_rev[i+cc[j]+1][j+1];
        }
    }

    /*
    printf("=\n");
    for(int i=2; i<=n+1; i++){
        for(int j=1; j<=k+1; j++) printf("%d ", dp_rev[i][j]);
        printf("\n");
    }
    */

    // Check white-ability
    for(int i=2; i<=n+1; i++){
        for(int j=0; j<=k; j++) ok_white[i] |= (dp[i-1][j] & dp_rev[i+1][j+1]);
    }

    // Check black-ability
    for(int j=1; j<=k; j++){
        int must_white = 0;
        for(int i=2; i<=2+cc[j]-1; i++){
            if(ss[i] == '_') must_white++;
        }
        int last_valid = 0;
        for(int i=2; i<=n+1-cc[j]+1; i++){
            if(must_white == 0 && ss[i-1] != 'X' && ss[i+cc[j]] != 'X' && dp[i-2][j-1] && dp_rev[i+cc[j]+1][j+1]){
                last_valid = i+cc[j]-1;
            }
            if(i <= last_valid) ok_black[i] = 1;
            must_white -= (ss[i] == '_');
            must_white += (ss[i+cc[j]] == '_');
        }
        for(int i=n+1-cc[j]+2; i<=n+1; i++) if(i <= last_valid) ok_black[i] = 1;
    }

    string res;

    for(int i=2; i<=n+1; i++){
        if(ss[i] != '.') res += ss[i];
        else if(ok_black[i] && ok_white[i]) res += '?';
        else if(ok_black[i]) res += 'X';
        else if(ok_white[i]) res += '_';
        else exit(1);
    }

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