Submission #143294

#	Time	Username	Problem	Language	Result	Execution time	Memory
143294		dolphingarlic	Paint By Numbers (IOI16_paint)	C++14	100 / 100	625 ms	98952 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>

using namespace std;

const int K = 105;
const int N = 200010;

string s;
vector<int> c;
int x[N], u[N];
int n, k, tot[N];
int dp[N][K];

int u_in_range(int l, int r) { return tot[r] - (l > 0 ? tot[l - 1] : 0); }

void update_x(int l, int r) { ++x[l], --x[r + 1]; }

void update_u(int l, int r) { ++u[l], --u[r + 1]; }

int call(int at, int block) {
    if (at >= n) return block == k;
    int &ret = dp[at][block];
    if (ret != -1) return ret;
    ret = 0;
    if (block == k) {
        if (s[at] == '_') {
            ret = call(at + 1, block);
            if (ret) update_u(at, at);
            return ret;
        } else if (s[at] == '.') {
            ret = call(at + 1, block);
            if (ret) update_u(at, at);
            return ret;
        } else {
            return ret = 0;
        }
    }
    if (s[at] == '_') {
        ret = call(at + 1, block);
        if (ret) update_u(at, at);
        return ret;
    }
    if (s[at] == 'X') {
        int nxt = at + c[block];
        if (nxt > n) return ret = 0;
        if (u_in_range(at, nxt - 1) > 0) {
            return ret = 0;
        }
        if (nxt < n and s[nxt] == 'X') {
            return ret = 0;
        }
        ret = call(nxt + 1, block + 1);
        if (ret) {
            if (nxt < n) {
                update_u(nxt, nxt);
            }
            update_x(at, nxt - 1);
        }
        return ret;
    }
    int one = call(at + 1, block);
    if (one) update_u(at, at);
    int two, nxt = at + c[block];
    if (nxt > n)
        two = 0;
    else if (u_in_range(at, nxt - 1) > 0) {
        two = 0;
    } else if (nxt < n and s[nxt] == 'X') {
        two = 0;
    } else {
        two = call(nxt + 1, block + 1);
        if (two) {
            if (nxt < n) {
                update_u(nxt, nxt);
            }
            update_x(at, nxt - 1);
        }
    }
    return ret = one | two;
}

string solve_puzzle(string s_in, vector<int> c_in) {
    s = s_in, c = c_in;
    n = s.size(), k = c.size();
    memset(dp, -1, sizeof dp);
    for (int i = 0; i < n; ++i) {
        if (i > 0) tot[i] = tot[i - 1];
        if (s[i] == '_') {
            ++tot[i];
        }
    }
    call(0, 0);
    string res = "";
    for (int i = 0; i < n; ++i) {
        if (i) {
            x[i] += x[i - 1];
            u[i] += u[i - 1];
        }
        if (x[i] and u[i])
            res += '?';
        else if (x[i])
            res += 'X';
        else
            res += '_';
    }
    return res;
}

• 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: 10 / 10