Submission #622408

#	Time	Username	Problem	Language	Result	Execution time	Memory
622408		Lucpp	Paint By Numbers (IOI16_paint)	C++17	80 / 100	2052 ms	880 KiB

paint

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

int n, k;
string s;
vector<int> c;

bool canSolve(){
    vector<vector<bool>> dp(n+1, vector<bool>(k+1, false));
    dp[0][0] = true;
    for(int i = 0; i < n; i++){
        if(s[i] == 'X') break;
        dp[i+1][0] = true;
    }
    int last_ = -1;
    for(int i = 0; i < n; i++){
        if(s[i] == '_') last_ = i;
        for(int j = 0; j < k; j++){
            int start = i+1-c[j];
            if(start > last_){
                if(start > 0) dp[i+1][j+1] = dp[start-1][j] && s[start-1] != 'X';
                else if(j == 0) dp[i+1][j+1] = true;
            }
            if(s[i] != 'X') dp[i+1][j+1] = dp[i+1][j+1] || dp[i][j+1];
        }
    }
    return dp[n][k];
}

string solve_puzzle(string S, vector<int> C){
    s = S;
    c = C;
    n = (int)S.size();
    k = (int)C.size();
    string ans(n, ' ');
    for(int i = 0; i < n; i++){
        if(s[i] != '.') ans[i] = s[i];
        else{
            s[i] = '_';
            bool w = canSolve();
            s[i] = 'X';
            bool b = canSolve();
            s[i] = '.';
            if(w && b) ans[i] = '?';
            else ans[i] = w?'_':'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: 0 / 10
• Subtask 7: 0 / 10