Submission #103055

#	Time	Username	Problem	Language	Result	Execution time	Memory
103055		Osama_Alkhodairy	Paint By Numbers (IOI16_paint)	C++17	0 / 100	2 ms	384 KiB

paint

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

const int N = 200005;
const int K = 105;

int n, k, w[N];
bool dp[N][K][2];
string s;
vector <int> c;

int get_sum(int l, int r){
    return w[r] - w[l - 1];
}
bool checkW(int idx){
    for(int j = 0 ; j <= k ; j++){
        if((j == 0 || dp[idx - 1][j][0]) && (j == k || dp[idx + 1][j + 1][1])){
            return 1;
        }
    }
    return 0;
}
std::string solve_puzzle(std::string S, std::vector<int> C) {
    s = S;
    c = C;
    n = s.size();
    k = c.size();
    c.insert(c.begin(), -1);
    s = ';' + s;
    for(int i = 1 ; i <= n ; i++)
        w[i] = w[i - 1] + (s[i] == '_');
    dp[0][0][0] = 1;
    for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= k ; j++){
            dp[i][j][0] = dp[i - 1][j][0];
            dp[i][j][0] |= (i - c[j] + 1 >= 1) && (get_sum(i - c[j] + 1, i) == 0) && (dp[max(0, i - c[j] - 1)][j - 1][0]);
        }
    }
    dp[n + 1][k + 1][1] = 1;
    for(int i = n ; i >= 1 ; i--){
        for(int j = k ; j >= 1 ; j--){
            dp[i][j][1] = dp[i + 1][j][1];
            dp[i][j][1] |= (i + c[j] - 1 <= n) && (get_sum(i, i + c[j] - 1) == 0) && (dp[min(n + 1, i + c[j] + 1)][j + 1][1]);
        }
    }
    vector <int> canB(n + 5);
    for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= k ; j++){
            if(dp[i][j][0] && (get_sum(i - c[j] + 1, i) == 0) && dp[max(0, i - c[j] - 1)][j - 1][0] && (j == k || dp[i + 2][j + 1][1])){
                canB[i - c[j] + 1]++;
                canB[i + 1]--;
            }
        }
    }
    for(int i = 1 ; i <= n ; i++)
        canB[i] += canB[i - 1];
    string ret = "";
    for(int i = 1 ; i <= n ; i++){
        if(s[i] == 'X' || s[i] == '_'){
            ret += s[i];
            continue;
        }
        int cur = 0;
        if(checkW(i)) cur |= 1;
        if(canB[i] > 0) cur |= 2;
        if(cur == 1) ret += '_';
        else if(cur == 2) ret += 'X';
        else ret += '?';
    }
    return ret;
}

• Subtask 1: 0 / 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