Submission #512994

#	Time	Username	Problem	Language	Result	Execution time	Memory
512994		sliviu	Paint By Numbers (IOI16_paint)	C++14	100 / 100	513 ms	163524 KiB

paint

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

using namespace std;


int canb[250002], cnt[250002], canw[250002], dpb[250002][102], dpa[250002][102];

string solve_puzzle(string s, vector<int> c) {
	string ans;
	int n = s.length(), k = c.size();
	s = '$' + s;
	for (int i = 1; i <= n + 1; ++i)
		cnt[i] = cnt[i - 1] + (s[i] == '_');
	dpb[0][0] = dpa[n + 1][k] = 1;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j <= k; ++j) {
			if (s[i + 1] != 'X')
				dpb[i + 1][j] |= dpb[i][j];
			if (j < k&& i + c[j] + 1 <= n && s[i + c[j] + 1] != 'X' && cnt[i] == cnt[i + c[j]])
				dpb[i + c[j] + 1][j + 1] |= dpb[i][j];
		}

	for (int i = n + 1; i > 1; --i)
		for (int j = 0; j <= k; ++j) {
			if (s[i - 1] != 'X')
				dpa[i - 1][j] |= dpa[i][j];
			if (j && i - c[j - 1] - 1 >= 1 && s[i - c[j - 1] - 1] != 'X' && cnt[i - 1] == cnt[i - c[j - 1] - 1])
				dpa[i - c[j - 1] - 1][j - 1] |= dpa[i][j];
		}

	for (int i = 0; i <= n; ++i)
		for (int j = 0; j <= k; ++j) {
			if (s[i] != 'X' && dpb[i][j] && dpa[i][j])
				canw[i] = 1;
			if (j < k && i + c[j] <= n && dpb[i][j] && dpa[i + c[j] + 1][j + 1] && cnt[i] == cnt[i + c[j]])
				++canb[i + 1], --canb[i + c[j] + 1];
		}
	for (int i = 1; i <= n; ++i)
		canb[i] += canb[i - 1];
	for (int i = 1; i <= n; ++i)
		ans += ((canw[i] && canb[i]) ? '?' : canw[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