Submission #789656

#	Time	Username	Problem	Language	Result	Execution time	Memory
789656		aymanrs	Paint By Numbers (IOI16_paint)	C++14	7 / 100	1 ms	292 KiB

paint

#include <bits/stdc++.h>
using namespace std;
string solve_puzzle(string s, vector<int> c){
    int k = c.size(), 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') dp[n-1][K-2] = true;
    else dp[n-1][K-2] = dp[n-1][K-1] = 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') Dp[n-1][K-2] = true;
    else Dp[n-1][K-2] = Dp[n-1][K-1] = 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;
}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:4:9: warning: unused variable 'k' [-Wunused-variable]
    4 |     int k = c.size(), n=s.size(), K;
      |         ^

• Subtask 1: 7 / 7
• Subtask 2: 0 / 3
• Subtask 3: 0 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10