Submission #581542

#	Time	Username	Problem	Language	Result	Execution time	Memory
581542		jeroenodb	Paint By Numbers (IOI16_paint)	C++14	100 / 100	584 ms	31228 KiB

paint

#include "paint.h"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int N = 2e5+1, K = 101, oo = 1e9;

string solve_puzzle(string s, vector<int> c) {
    s = '_'+s+'_';
    int n = s.size(), k = c.size();
    vi prefW(n+1);
    auto good = [&](int st, int id) {
        // check if we can place block c[id] at place st
        int e = st+c[id];
        if(e>=n) return false;
        if(prefW[e]-prefW[st]!=0) return  false;
        if(s[e]=='X') return false;
        if(s[st-1]=='X') return false;
        return true;
    };
    // compute prefcan and sufcan
    vector<vector<bool>> pref,suf;
    for(int rep=0;rep<2;++rep) {
        reverse(all(s));
        reverse(all(c));
        swap(pref,suf);
        for(auto& b : suf) {
            for(int i=0;i<=k/2;++i) {
                swap(b[i],b[k-i]);
            }
        }
        reverse(all(suf));
        fill(all(prefW),0);
        for(int i=0;i<n;++i) {
            prefW[i+1] = prefW[i]+(s[i]=='_');
        }
        pref.assign(n,vector<bool>(k+1));
        pref[0][0]=1;
        for(int i=1;i<n;++i) {
            for(int j=0;j<=k;++j) {
                pref[i][j] = pref[i][j] or (pref[i-1][j] and s[i-1]!='X');
                if(!pref[i][j] or j==k) continue;
                if(good(i,j)) {
                    int to = i+c[j]+1;
                    if(to<n) pref[to][j+1] = true;
                }
            }
        }
        

    }
    // calculate answer
    string res(n,'?');
    vi p(n+1);
    // handle blacks
    for(int j=0;j<k;++j) {
        int l = c[j];
        for(int i=1;i+l<n;++i) if( good(i,j)) {
            if(pref[i][j] and suf[i+l-1][j+1]) {
                p[i]++,p[i+l]--;
            }
        }
    }
    partial_sum(all(p),p.begin());
    for(int i=0;i<n;++i) {
        if(!p[i]) res[i]='_';
    }
    // handle whites
    for(int i=1;i<n-1;++i) {
        if(res[i]=='?') {
            bool g= false;
            // not in b
            for(int j=0;j<=k and !g;++j) {
                if(pref[i+1][j] and suf[i-1][j]) {
                    g=true;
                }
            }
            if(!g) res[i]='X';
        }
    }
    return res.substr(1,n-2);
    
}

• 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