Submission #762760

#	Time	Username	Problem	Language	Result	Execution time	Memory
762760		_martynas	Paint By Numbers (IOI16_paint)	C++11	59 / 100	1 ms	724 KiB

paint

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

using namespace std;

const int mxn = 2e5+5;
const int mxk = 105;

int n, k;
int pref_b[mxn], pref_w[mxn];
bool dp[mxk][mxn], dp_pref[mxk][mxn];
bool must_b[mxn], can_b[mxn];

bool check(int pref[], int l, int r) {
    return pref[r] == pref[l-1];
}

// TODO: handle case where there are Xs on the right side and invalidate some ending positions
string solve_puzzle(string s, vector<int> C) {
    n = s.size(), k = C.size();
    s = "$"+s;
    C.insert(C.begin(), -1);
    for(int i = 1; i <= n; i++) {
        pref_b[i] = pref_b[i-1]+(s[i]=='X');
        pref_w[i] = pref_w[i-1]+(s[i]=='_');
    }
    dp[0][0] = true;
    for(int i = C[0]; i <= n; i++) {
        if(s[i] != 'X') {
            dp_pref[0][i] = dp_pref[0][i-1];
        }
        dp_pref[0][i] |= dp[0][i];
    }
    for(int f = 1; f <= k; f++) {
        for(int i = C[f]; i <= n; i++) {
            if(((i > C[f] && dp_pref[f-1][i-C[f]-1]) || (i == C[f] && f == 1))
                && check(pref_w, i-C[f]+1, i) && check(pref_b, i-C[f], i-C[f])) {
                dp[f][i] = true;
            }
        }
        for(int i = C[f]; i <= n; i++) {
            if(s[i] != 'X') {
                dp_pref[f][i] = dp_pref[f][i-1];
            }
            dp_pref[f][i] |= dp[f][i];
        }
    }
    // mark certain X
    for(int f = k, rmost_start = n; f > 0; f--) {
        int l = 0, r = n;
        int rmost = 0;
        for(int i = 0; i <= rmost_start; i++) {
            if(dp[f][i]) {
                r = min(r, i);
                l = max(l, i-C[f]+1);
                rmost = max(rmost, i);
            }
        }
        for(int i = l; i <= r; i++) {
            must_b[i] = true;
        }
        rmost_start = rmost-C[f]-1;
    }
    // mark possible X
    for(int f = k, rmost_start = n; f > 0; f--) {
        int cnt = 0;
        int rmost = 0;
        for(int i = rmost_start; i >= 0; i--) {
            if(dp[f][i]) {
                cnt = C[f];
                rmost = max(rmost, i);
            }
            if(cnt > 0) can_b[i] = true;
            cnt--;
        }
        rmost_start = rmost-C[f]-1;
    }
    string ans(n, '?');
    for(int i = 1; i <= n; i++) {
        if(!can_b[i]) {
            ans[i-1] = '_';
        }
        else if(must_b[i]) {
            ans[i-1] = 'X';
        }
        if(s[i] == '_') {
            ans[i-1] = '_';
        }
        if(s[i] == 'X') {
            ans[i-1] = 'X';
        }
    }
    return ans;
}
/*
..........
2
3 4

........
2
3 4

..._._....
1
3

.X........
1
3
*/

• 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