Submission #103340

#	Time	Username	Problem	Language	Result	Execution time	Memory
103340		Osama_Alkhodairy	Paint By Numbers (IOI16_paint)	C++17	90 / 100	2069 ms	177780 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], b[N], dp[N][K][2];
string s;
vector <int> c;

int sum_b(int l, int r){
    return b[r] - b[l - 1];
}
int sum_w(int l, int r){
    return w[r] - w[l - 1];
}
int solve0(int i, int j){
    if(i <= 0) return j == 0;
    if(j == 0) return sum_b(1, i) == 0;
    int &ret = dp[i][j][0];
    if(ret != -1) return ret;
    ret = 0;
    if(s[i] == 'X' || s[i] == '.'){
        if(i - c[j] + 1 >= 1 && sum_w(i - c[j] + 1, i) == 0 && s[i - c[j]] != 'X'){
            ret |= solve0(i - c[j] - 1, j - 1);
        }
    }
    if(s[i] == '_' || s[i] == '.'){
        ret |= solve0(i - 1, j);
    }
    return ret;
}
int solve1(int i, int j){
    if(i > n) return j == k + 1;
    if(j == k + 1) return sum_b(i, n) == 0;
    int &ret = dp[i][j][1];
    if(ret != -1) return ret;
    ret = 0;
    if(s[i] == 'X' || s[i] == '.'){
        if(i + c[j] - 1 <= n && sum_w(i, i + c[j] - 1) == 0 && s[i + c[j]] != 'X'){
            ret |= solve1(i + c[j] + 1, j + 1);
        }
    }
    if(s[i] == '_' || s[i] == '.'){
        ret |= solve1(i + 1, j);
    }
    return ret;
}
bool check_w(int idx){
    for(int j = 0 ; j <= k ; j++){
        if(solve0(idx - 1, j) && solve1(idx + 1, j + 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;
    s = s + ';';
    for(int i = 1 ; i <= n ; i++)
        w[i] = w[i - 1] + (s[i] == '_');
    for(int i = 1 ; i <= n ; i++)
        b[i] = b[i - 1] + (s[i] == 'X');
    memset(dp, -1, sizeof dp);
    vector <int> can_b(n + 5);
    for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= k ; j++){
            if(i - c[j] + 1 >= 1 && sum_w(i - c[j] + 1, i) == 0 && s[i - c[j]] != 'X' && s[i + 1] != 'X' &&
               solve0(i - c[j] - 1, j - 1) && solve1(i + 2, j + 1)){
                can_b[i - c[j] + 1]++;
                can_b[i + 1]--;
            }
        }
    }
    for(int i = 1 ; i <= n ; i++)
        can_b[i] += can_b[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(check_w(i)) cur |= 1;
        if(can_b[i] > 0) cur |= 2;
        if(cur == 1) ret += '_';
        else if(cur == 2) ret += 'X';
        else ret += '?';
    }
    return ret;
}

• 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