Submission #436261

#	Time	Username	Problem	Language	Result	Execution time	Memory
436261		qwerasdfzxcl	Paint By Numbers (IOI16_paint)	C++14	32 / 100	1 ms	296 KiB

paint

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

using namespace std;
typedef long long ll;
string str, ans;
vector<int> a;
int pt[101], prv[101], cnt[101], N, K, X, cntx;

bool valid(int x, int y){
    return ((x-1<0 || str[x-1]!='X') && (y>=N || str[y]!='X'));
}

void update(int x, int y, int l, int mx = 1e9){
    if (x==y) return;
    for (int i=max(x+l, y);i<y+l;i++) if (i<=mx) ans[i] = '?';
    for (int i=x;i<min(x+l, y);i++) if (i<=mx){
        if (ans[i]=='X') ans[i] = 'X';
        else ans[i] = '?';
    }
}

bool init(int pos, int t){
    for (int i=pt[t]-1;i>=pos;i--){
        pt[t] = i;
        if (str[i]=='X') cntx++;
        if (str[i]=='_') cnt[t]++;
        if (i+a[t]>N) continue;
        if (!cnt[i] && valid(i, i+a[t])){
            if ((t==K-1 || init(i+a[t]+1, t+1)) && cntx==X) return 1;
        }
        if (i>pos){
            if (str[i+a[t]-1]=='_') cnt[t]--;
            if (str[i+a[t]-1]=='X') cntx--;
        }
    }
    return 0;
}

bool solve(int pos, int t){
    //cout << pos << ' ' << t << ' ' << ans << '\n';
    if (pos!=prv[t]){
        assert(prv[t]-pos==1);
        if (str[pos+a[t]]=='_') cnt[t]--;
        if (str[pos+a[t]]=='X') cntx--;
        if (str[pos]=='_') cnt[t]++;
        if (str[pos]=='X') cntx++;
    }
    prv[t] = pos;
    if (!cnt[t] && valid(pos, pos+a[t])){
        bool ret = 0;
        if (cntx==X){
            update(pos, pt[t], a[t]);
            ret = 1;
        }
        if (t<K-1){
            for (int i=prv[t+1];i>=pos+a[t]+1;i--) if (solve(i, t+1)){
                if (!ret) update(pos, pt[t], a[t], i);
                ret = 1;
            }
        }
        if (ret) pt[t] = pos;
        return ret;
    }
    return 0;
}

string solve_puzzle(string s, vector<int> c) {
    str = s, a = c, N = s.size(), K = c.size();
    ans.resize(s.size());
    fill(pt, pt+K, N);
    for (int i=0;i<N;i++) if (str[i]=='X') X++;
    for (int i=0;i<K;i++){
        for (int j=0;j<a[i];j++) if (str[N-a[i]+j]=='_') cnt[i]++;
    }
    assert(init(0, 0));
    fill(ans.begin(), ans.end(), '_');
    for (int i=0;i<K;i++) fill(ans.begin()+pt[i], ans.begin()+pt[i]+a[i], 'X');
    //cout << ans << '\n';
    for (int i=0;i<K;i++) prv[i] = pt[i];
    for (int i=pt[0];i>=0;i--) solve(i, 0);
    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