Submission #1025066

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025066		Tonyl	Paint By Numbers (IOI16_paint)	C++17	59 / 100	1 ms	600 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(x) for (auto &a : x)
#define D(x) //cerr << #x << ": " << x << endl;

vi fits;
vi rev_fits;

string s;
vi c;
int n, m;

void calc_fits() {
    fits = vi(n, 0);
    REP(i, n) {
        if (s[i] == '_') {fits[i] = fits[max(0,i-1)]; continue;}
        
        REP(d, m) {
            // try putting d
            if (c[d] > i+1) continue;
            for (int j = i+1-c[d]; j < i; j++) {
                if (s[j] == '_') 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] != d) goto skip;}
            else if (d != 0) goto skip;

            fits[i] = d+1;

            skip:;
        }

        if (s[i] != 'X') fits[i] = max(fits[i],fits[max(0,i-1)]);
    }
}

bool can_white(int i) {
    int left = 0; int right = 0;
    if (i > 0) left = fits[i-1];
    if (i < n-1) right = rev_fits[i+1];
    return left + right >= m; // simplified!
}

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;
            int left = 0; int right = 0;
            // fits?
            if (start < 0) continue;
            if (end > n-1) continue;
            // is clear?
            for (int j = start; j <= end; j++) {
                if (s[j] == '_') 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 < d) goto fail;
            if (right < 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_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: 27 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10