Submission #137375

#	Time	Username	Problem	Language	Result	Execution time	Memory
137375		choikiwon	Paint By Numbers (IOI16_paint)	C++17	100 / 100	1276 ms	257144 KiB

paint

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

const int maxn = 200010;

int N, K;
char S[maxn];
int C[maxn], psum1[maxn], psum2[maxn], chk[maxn][2];
int sum[111][maxn];

int calc(int l, int r, int *psum) {
    if(l > r) return 0;
    return psum[r] - (l? psum[l - 1] : 0);
}

int dp1[maxn][111];
int dp2[maxn][111];

void fill_dp() {
    dp1[0][0] = 1;
    for(int i = 1; i <= N; i++) {
        for(int j = 0; j <= K; j++) {
            if(S[i] == 'X') {
                continue;
            }
            dp1[i][j] |= dp1[i - 1][j];
            if(j && i - C[j] >= 1 && calc(i - C[j], i - 1, psum2) == 0) dp1[i][j] |= dp1[i - C[j] - 1][j - 1];
        }
    }
    dp2[N + 1][K + 1] = 1;
    for(int i = N; i >= 1; i--) {
        for(int j = 1; j <= K + 1; j++) {
            if(S[i] == 'X') {
                continue;
            }
            dp2[i][j] |= dp2[i + 1][j];
            if(j <= K && i + C[j] <= N && calc(i + 1, i + C[j], psum2) == 0) dp2[i][j] |= dp2[i + C[j] + 1][j + 1];
        }
    }
}

std::string solve_puzzle(std::string s, std::vector<int> c) {
    N = s.size();
    K = c.size();
    for(int i = 1; i <= N; i++) {
        S[i] = s[i - 1];
    }
    for(int i = 1; i <= K; i++) {
        C[i] = c[i - 1];
    }

    for(int i = 1; i <= N; i++) {
        psum1[i] = S[i] == 'X';
        psum2[i] = S[i] == '_';
        psum1[i] += psum1[i - 1];
        psum2[i] += psum2[i - 1];
    }

    fill_dp();

    for(int i = 1; i <= N; i++) {
        if(S[i] == 'X') chk[i][1] = 1;
        if(S[i] == '_') chk[i][0] = 1;
    }
    for(int i = 1; i <= N; i++) if(S[i] == '.') {
        for(int j = 0; j <= K; j++) {
            if(dp1[i][j] & dp2[i][j + 1]) {
                chk[i][0] = 1;
                break;
            }
        }
    }

    for(int i = 1; i <= K; i++) {
        for(int j = 0; j <= N - C[i]; j++) {
            sum[i][j] = dp1[j][i - 1] & dp2[j + C[i] + 1][i + 1] & calc(j + 1, j + C[i], psum2) == 0;
        }
        for(int j = 1; j <= N + 1; j++) {
            sum[i][j] += sum[i][j - 1];
        }
    }

    for(int i = 1; i <= N; i++) if(S[i] == '.') {
        for(int j = 1; j <= K; j++) {
            if(calc(max(0, i - C[j]), i - 1, sum[j])) {
                chk[i][1] = 1;
                break;
            }
        }
    }

    string ret;
    for(int i = 1; i <= N; i++) {
        if(chk[i][1] == chk[i][0]) ret.push_back('?');
        else if(chk[i][1]) ret.push_back('X');
        else ret.push_back('_');
    }
    return ret;
}

Compilation message (stderr)

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:77:97: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
             sum[i][j] = dp1[j][i - 1] & dp2[j + C[i] + 1][i + 1] & calc(j + 1, j + C[i], psum2) == 0;
                                                                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

• 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