Submission #402440

#	Time	Username	Problem	Language	Result	Execution time	Memory
402440		danielcm585	Paint By Numbers (IOI16_paint)	C++14	100 / 100	697 ms	183216 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5;
const int K = 1e2;
int n, k;
int x[K+5], b[N+5], w[N+5];
int memo[N+5][K+5], vis[N+5][K+5];
string a;
set<int> st;

bool white(int l, int r) {
    if (st.empty()) return 0;
    auto it = st.lower_bound(l);
    if (it != st.end() && *it <= r) return 1;
    return 0;
}

int dp(int pos, int id) {
    if (pos >= n) return (id == k);
    if (memo[pos][id] != -1) return memo[pos][id];
    int ret = 0;
    if (a[pos] != 'X') ret |= dp(pos+1,id);
    if (pos+x[id]-1 < n && id < k && !white(pos,pos+x[id]-1) && a[pos+x[id]] != 'X') {
        ret |= dp(pos+x[id]+1,id+1);
    }
    // cout << ">> " << pos << ' ' << id << " -> " << ret << '\n';
    return memo[pos][id] = ret;
}

void bt(int pos, int id) {
    if (pos >= n || vis[pos][id]) return;
    vis[pos][id] = 1;
    if (a[pos] != 'X' && dp(pos+1,id)) {
        w[pos] = 1;
        bt(pos+1,id);
    }
    if (pos+x[id]-1 < n && id < k && !white(pos,pos+x[id]-1) && a[pos+x[id]] != 'X' && dp(pos+x[id]+1,id+1)) {
        b[pos]++; b[pos+x[id]]--;
        w[pos+x[id]] = 1;
        bt(pos+x[id]+1,id+1);
    }
}

string solve_puzzle(string s, vector<int> c) {
    n = s.length(); k = c.size(); a = s;
    for (int i = 0; i < n; i++) {
        if (s[i] == '_')  st.insert(i);
    }
    for (int i = 0; i < k; i++) x[i] = c[i];
    memset(memo,-1,sizeof(memo));
    bt(0,0);
    string ans;
    int cur = 0;
    for (int i = 0; i < n; i++) {
        cur += b[i];
        if (w[i] && cur) ans += '?';
        else ans += (w[i] ? '_' : 'X');
    }
    return ans;
}

• 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