Submission #426388

#	Time	Username	Problem	Language	Result	Execution time	Memory
426388		SuhaibSawalha1	Paint By Numbers (IOI16_paint)	C++17	100 / 100	874 ms	94576 KiB

paint

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

const int N = 2e5, M = 100;
int canb[3 * N], canw[3 * N], dp[N][M], n, m, cnt[N];
vector<int> c;
string s;

bool calc (int i = 0, int j = 0) {
	if (i >= n) {
		return j == m;
	}
	int &ret = dp[i][j];
	if (~ret) {
		return ret;
	}
	ret = 0;
	if (s[i] != 'X' && calc(i + 1, j)) {
		canw[i] = ret = 1;
	}
	if (j != m && cnt[i] >= c[j] && s[i] != '_' && (i + c[j] >= n || s[i + c[j]] != 'X') && calc(i + c[j] + 1, j + 1)) {
		ret = 1;
		++canb[i];
		--canb[i + c[j]];
		canw[i + c[j]] = 1;
	}
	return ret;
}

string solve_puzzle(string s, vector<int> c) {
	::c = c;
	::s = s;
	n = s.size();
	m = c.size();
	int cn = 0;
	for (int i = n - 1; ~i; --i) {
		cn += s[i] != '_' ? 1 : -cn;
		cnt[i] = cn;
	}
	memset(dp, -1, sizeof dp);
	assert(calc());
	for (int i = 0; i < n; ++i) {
		if (i) {
			canb[i] += canb[i - 1];
		}
		if (canb[i] && canw[i]) {
			s[i] = '?';
		}
		else if (canb[i]) {
			s[i] = 'X';
		}
		else {
			s[i] = '_';
		}
	}
	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