Submission #548214

#	Time	Username	Problem	Language	Result	Execution time	Memory
548214		ACE_	Paint By Numbers (IOI16_paint)	C++14	100 / 100	302 ms	166692 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
#include <cstdlib>
const int N = 2e5 + 5, K = 105;
int dp[N][K], dp2[N][K], ok[N];
std::string solve_puzzle(std::string s, std::vector<int> c) {
	int n = s.size();
	s = '1' + s + '1';
	int m = c.size();
	int prev = 0;
	dp[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		if (s[i] == '_') {
			prev = i;
			for (int j = 0; j <= m; j++) dp[i][j] = dp[i - 1][j];
			continue;
		}
		if (s[i] == '.')
			for (int j = 0; j <= m; j++) dp[i][j] = dp[i - 1][j];

		for (int j = 1; j <= m; j++) {
			if (c[j - 1] <= i && prev <= i - c[j - 1] && s[i - c[j - 1]] != 'X') {

				dp[i][j] |= dp[max(0, i - c[j - 1] - 1)][j - 1];
			}
		}
	}
	prev = n + 1;
	dp2[n + 1][m + 1] = 1;
	for (int i = n; i >= 1; i--) {
		if (s[i] == '_') {
			prev = i;
			for (int j = 1; j <= m + 1; j++) dp2[i][j] = dp2[i + 1][j];
			continue;
		}
		if (s[i] == '.')
			for (int j = 1; j <= m + 1; j++) dp2[i][j] = dp2[i + 1][j];

		for (int j = 1; j <= m; j++) {
			if (c[j - 1] + i - 1 <= n && prev > c[j - 1] + i - 1 && s[i + c[j - 1]] != 'X') {
				dp2[i][j] |= dp2[min(n + 1, i + c[j - 1] + 1)][j + 1];
				if ((dp2[min(n + 1, i + c[j - 1] + 1)][j + 1] && dp[max(0, i - 2)][j - 1] && s[i - 1] != 'X')) {
					ok[i]++; ok[i + c[j - 1]]--;
				}
			}
		}
	}
	string ans = "";
	for (int i = 1; i <= n; i++) {
		ok[i] += ok[i - 1];
		if (s[i] == 'X') ans += 'X';
		else if (s[i] == '_') ans += '_';
		else {
			if (!ok[i]) ans += '_';
			else {
				int f = 0;
				for (int j = 0; j <= m; j++) {
					f |= dp[i - 1][j] & dp2[i + 1][j + 1];
				}
				if (!f) ans += 'X';
				else ans += '?';
			}
		}
	}
	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