Submission #328488

#	Time	Username	Problem	Language	Result	Execution time	Memory
328488		nikatamliani	Paint By Numbers (IOI16_paint)	C++14	100 / 100	826 ms	259556 KiB

paint

// #include "paint.h"
#include <bits/stdc++.h>
using namespace std;
int sum(int l, int r, vector<int>& p) {
	l = max(0, l);
	r = min(r, (int)p.size() - 1);
	if(l > r) return 0; 
	return p[r] - (l > 0 ? p[l - 1] : 0);
}
std::string solve_puzzle(std::string s, std::vector<int> a) {
	int n = s.size(), m = a.size();
	a.insert(a.begin(), 0);
	s = "@" + s + "@";
	vector<vector<vector<int>>>dp(2, vector<vector<int>>(n + 2, vector<int>(m + 2, 0)));
	vector<int>p(n + 2);
	for(int i = 1; i <= n; ++i) {
		p[i] = p[i - 1] + (s[i] == '_');
	}
	for(int i = 0; i <= n + 1; ++i) {
		if(s[i] == 'X') break;
		dp[0][i][0] = 1;
	}
	for(int i = n + 1; i >= 0; --i) {
		if(s[i] == 'X') break;
		dp[1][i][m + 1] = 1;
	}
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			int start = i - a[j] + 1; 
			if(s[i] != 'X') {
			    dp[0][i][j] |= dp[0][i - 1][j]; 
			}
			if(s[i] != '_' && start >= 1 && sum(start, i, p) == 0) {
				if(start == 1) {
					dp[0][i][j] |= (j == 1); 
				} else if(s[start - 1] != 'X') {
					dp[0][i][j] |= dp[0][start - 2][j - 1];
				}
			}
		}
	}
	for(int i = n; i >= 1; --i) {
		for(int j = m; j >= 1; --j) {
			int end = i + a[j] - 1;
			if(s[i] != 'X') {
				dp[1][i][j] |= dp[1][i + 1][j];
			}
			if(s[i] != '_' && end <= n && sum(i, end, p) == 0) {
				if(end == n) {
					dp[1][i][j] |= (j == m);
				} else if(s[end + 1] != 'X') {
					dp[1][i][j] |= dp[1][end + 2][j + 1];
				}
			}
		}
	}
	vector<bool> can_white(n + 2), can_black(n + 2);
	vector<int> pref(n + 2);
	for(int i = 1; i <= n; ++i) {
		if(s[i] == 'X') continue;
		for(int j = 0; j <= m; ++j) {
			bool check_left = 0, check_right = 0; 
			check_left = dp[0][i - 1][j];
			check_right = dp[1][i + 1][j + 1];
			if(check_left && check_right) {
				can_white[i] = true;
			}
		}
	}
	for(int i = 1; i <= n; ++i) {
		if(s[i] == '_') continue;
		for(int j = 1; j <= m; ++j) {
			int start = i - a[j] + 1; 
			if(start <= 0) continue;
			if(start > 1 && s[start - 1] == 'X') continue; 
			bool check_left = 0, check_right = 0, check_me = 0;
			if(start - 2 < 0) {
				if(j == 1) check_left = 1; 
			} else {
				check_left = dp[0][start - 2][j - 1] && (s[start - 1] != 'X');
			}
			if(i + 2 > n + 1) {
				if(j == m) check_right = 1;
			} else {
				check_right = dp[1][i + 2][j + 1] && (s[i + 1] != 'X');
			}
			if(sum(start, i, p) == 0) {
				check_me = 1;
			}
			if(check_left && check_me && check_right) {
				++pref[start];
				--pref[i + 1];
			}
		}
	}
	for(int i = 1; i <= n; ++i) {
		pref[i] += pref[i - 1];
		can_black[i] = pref[i] > 0; 
	}
	string answer = "";
	for(int i = 1; i <= n; ++i) {
		if(can_white[i] && can_black[i]) {
			answer += '?';
		} else {
			if(can_white[i]) {
				answer += '_';
			} else {
				answer += 'X';
			}
		}
	}
	return answer;
}

• 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