Submission #120713

#	Time	Username	Problem	Language	Result	Execution time	Memory
120713		arman_ferdous	Paint By Numbers (IOI16_paint)	C++17	100 / 100	645 ms	102520 KiB

paint

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

using si = short int;
const int N = 2e5+10;
const int K = 105;

int n, sum[N], can[N], sz[K], Xcnt[N];
string s;
si dp[2][K][N];

int res[2][N];

si DP(int prev, int blc, int pos) {
	if(blc < 0) {
		if(pos < 1) return 1;
		if(Xcnt[pos] == 0) {
			res[0][1]++;
			res[0][pos + 1]--;
			return 1;
		}
		return 0;
	}
	if(pos < 1) return 0;

	si &ret = dp[prev][blc][pos];
	if(ret != -1) return ret;

	if(s[pos] == 'X') {
		if(prev == 0) {
			if(pos - sz[blc] < 0 || sum[pos] - sum[pos - sz[blc]] > 0) return ret = 0;
			si got = DP(1, blc - 1, pos - sz[blc]);
			if(got == 1) {
				res[1][pos - sz[blc] + 1]++;
				res[1][pos + 1]--;
			}
			return ret = got;
		}
		return ret = 0;
	}
	if(s[pos] == '_') {
		si got = DP(0, blc, pos - 1);
		if(got == 1) {
			res[0][pos]++;
			res[0][pos + 1]--;
		}
		return ret = got;
	}

	si zero = DP(0, blc, pos - 1);
	if(zero == 1) {
		res[0][pos]++;
		res[0][pos + 1]--;
	}
	si one;
	if(prev == 1 || pos - sz[blc] < 0 || sum[pos] - sum[pos - sz[blc]] > 0) one = 0;
	else {
		one = DP(1, blc - 1, pos - sz[blc]);
		if(one == 1) {
			res[1][pos - sz[blc] + 1]++;
			res[1][pos + 1]--;
		}
	}
	return ret = (one | zero);
}

string solve_puzzle(string _s, vector<int> c) {
    s = "#" + _s; n = s.size();
    for(int i = 0; i < (int)c.size(); i++)
    	sz[i] = c[i];
    for(int i = 1; i < n; i++) {
    	sum[i] = sum[i - 1] + (s[i] == '_');
    	Xcnt[i] = Xcnt[i - 1] + (s[i] == 'X');
    }

    memset(dp, -1, sizeof dp);
    DP(0, (int)c.size() - 1, n - 1);

    for(int i = 1; i < n; i++) {
    	res[0][i] += res[0][i - 1];
    	res[1][i] += res[1][i - 1];
    	if(res[0][i] && res[1][i]) _s[i - 1] = '?';
    	else if(res[0][i]) _s[i - 1] = '_';
    	else _s[i - 1] = 'X';
    }
   	return _s;
}

• 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