Submission #1029438

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029438		Tonyl	Paint By Numbers (IOI16_paint)	C++17	32 / 100	6 ms	608 KiB

paint

#include "paint.h"
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define REP(i,n) for (int i = 0; i < n; i++)
#define all(x) (x).begin(), (x).end()
#define trav(a,x) for (auto &a : x)
#define D(x) //cerr << #x << ": " << x << endl;

vector<set<int>> fits;
vector<set<int>> rev_fits;

string s;
vi c;
int n, m;

vi pref_;

bool contains_(int l, int r) {
    if (l > r) return false;
    return (pref_[r+1]-pref_[l]) > 0;
}

void calc_pref() {
    pref_.assign(n+1,0);
    int count = 0;
    REP(i,n) {
        if (s[i] == '_') count++;
        pref_[i+1] = count;
    }
}

void calc_fits() {
    fits.assign(n, {});
    bool had_x = false;
    REP(i, n) {
        if (s[i] == 'X') had_x = true;
        if (!had_x) fits[i].insert(0);
        if (s[i] == '_') {fits[i] = fits[max(0,i-1)]; continue;}

        REP(d, m) {
            // try putting d
            if (c[d] > i+1) continue;
            if (contains_(i+1-c[d], i-1)) {
                goto skip;
            }
            if (i-c[d] >= 0 && s[i-c[d]] == 'X') goto skip;
            if (i-c[d]-1 >= 0) {if (!fits[i-c[d]-1].count(d)) goto skip;}
            else if (d != 0) goto skip;

            fits[i].insert(d+1);

            skip:;
        }

        if (s[i] != 'X' && i != 0) {
            trav(el, fits[i-1]) {fits[i].insert(el);}
        }
    }
}

bool can_white(int i) {
    set<int> left = {0}; set<int> right = {0};
    if (i > 0) left = fits[i-1];
    if (i < n-1) right = rev_fits[i+1];
    auto b = right.rbegin();
    trav(a, left) {
        while (b != right.rend() && (a + *b) > m) b++;
        if (b == right.rend()) break;
        if (a + *b == m) return true;
    }
    return false;
}

bool can_black(int i) {
    D(i);
    REP(d, m) {
        for (int fx = -c[d]+1; fx <= 0; fx++) {
            D(fx);
            int start = i+fx;
            int end = start+c[d]-1;
            set<int> left = {0}; set<int> right = {0};
            // fits?
            if (start < 0) continue;
            if (end > n-1) continue;
            // is clear?
            if (contains_(start, end)) goto fail;
            //cerr << "clr\n";
            // are bounds ok?
            if (start > 0 && s[start-1] == 'X') goto fail;
            if (end < n-1 && s[end+1] == 'X') goto fail;
            // okay, what fits?
            if (start > 1) left = fits[start-2];
            if (end < n-2) right = rev_fits[end+2];
            D(left); D(right);
            // does it fit together?
            if (!left.count(d)) goto fail;
            if (!right.count(m-1-d)) goto fail;

            // yay!
            return true;
            fail:;
        }
    }
    return false;
}

std::string solve_puzzle(std::string s_, std::vector<int> c_) {
    s = s_; c = c_; n = s.size(); m = c.size();
    calc_pref();
    calc_fits();
    swap(fits, rev_fits);
    reverse(all(s)); reverse(all(c));
    calc_fits();
    swap(fits, rev_fits);
    reverse(all(s)); reverse(all(c));
    reverse(all(rev_fits));

    /*REP(i, n) {
        cerr << fits[i] << " ";
    }
    cerr << endl;

    REP(i, n) {
        cerr << rev_fits[i] << " ";
    }
    cerr << endl;*/

    string ans(n, '?');
    REP(i, n) {
        if (s[i] != '.') ans[i] = s[i];
        else {
            if (!can_white(i)) ans[i] = 'X';
            if (!can_black(i)) ans[i] = '_';
            if (!can_white(i) && !can_black(i)) ans[i] = '!';
        }
    }
    return ans;
}

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