Submission #789658

#	Time	Username	Problem	Language	Result	Execution time	Memory
789658		aymanrs	Paint By Numbers (IOI16_paint)	C++14	90 / 100	337 ms	524288 KiB

paint

#include <bits/stdc++.h>
using namespace std;
string solve_puzzle(string s, vector<int> c){
    int n=s.size(), K;
    string C, S = s, R;
    for(int i : c){
        C.push_back('_');
        C += string(i, 'X');
    }
    C.push_back('_');
    R = C;
    reverse(S.begin(), S.end());
    reverse(R.begin(), R.end());
    K = C.size();
    bool dp[n+1][K+1], Dp[n+1][K+1];
    for(int i = 0;i <= n;i++) for(int j = 0;j <= K;j++) dp[i][j] = Dp[i][j] = false;
    dp[n][K-1] = true;
    if(s.back() == '_') dp[n-1][K-1] = true;
    else if(s.back() == 'X') {
        if(C[K-3] == '_') dp[n-1][K-3] = true;
        dp[n-1][K-2] = true;
    } else {
        dp[n-1][K-2] = dp[n-1][K-1] = true;
        if(C[K-3] == '_') dp[n-1][K-3] = true;
    }
    for(int i = n-2;i >= 0;i--){
        for(int j = K-1;j >= 0;j--){
            if((s[i] == '_' || s[i] == '.') && C[j] == '_') dp[i][j] |= dp[i+1][j];
            if(s[i] == 'X' || s[i] == '.'){
                if(C[j] == '_') dp[i][j] |= dp[i][j+1];
                else {
                    if(C[j+1] == '_') {
                        if(s[i+1] == '_' || s[i+1] == '.') dp[i][j] |= dp[i+2][j+1];
                    } else dp[i][j] |= dp[i+1][j+1];
                }
            }
        }
    }
    Dp[n][K-1] = true;
    if(S.back() == '_') Dp[n-1][K-1] = true;
    else if(S.back() == 'X') {
        if(R[K-3] == '_') Dp[n-1][K-3] = true;
        Dp[n-1][K-2] = true;
    } else {
        Dp[n-1][K-2] = Dp[n-1][K-1] = true;
        if(R[K-3] == '_') Dp[n-1][K-3] = true;
    }
    for(int i = n-2;i >= 0;i--){
        for(int j = K-1;j >= 0;j--){
            if((S[i] == '_' || S[i] == '.') && R[j] == '_') Dp[i][j] |= Dp[i+1][j];
            if(S[i] == 'X' || S[i] == '.'){
                if(R[j] == '_') Dp[i][j] |= Dp[i][j+1];
                else {
                    if(R[j+1] == '_') {
                        if(S[i+1] == '_' || S[i+1] == '.') Dp[i][j] |= Dp[i+2][j+1];
                    } else Dp[i][j] |= Dp[i+1][j+1];
                }
            }
        }
    }
    string ans(n, '?');
    for(int i = 0;i < n;i++){
        if(s[i] != '.'){
            ans[i] = s[i];
            continue;
        }
        bool w = false, b = false;
        for(int j = 0;j < K;j++){
            if(C[j] == '_'){
                w |= dp[i+1][j] && Dp[n-i][K-j-1];
            } else {
                b |= dp[i][j] && Dp[n-i-1][K-j-1];
            }
        }
        if(w ^ b) {
            if(w) ans[i] = '_';
            else ans[i] = '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: 0 / 10