Submission #614267

#	Time	Username	Problem	Language	Result	Execution time	Memory
614267		Temmie	Paint By Numbers (IOI16_paint)	C++17	100 / 100	1967 ms	108464 KiB

paint

#include <bits/stdc++.h>

std::string solve_puzzle(std::string s, std::vector <int> c) {
	int n = s.size();
	int k = c.size();
	std::vector <std::vector <int>> dp(n, std::vector <int> (k + 1, -1));
	std::vector <int> start_black(n, 0);
	std::vector <int> start_white(n, 0);
	std::vector <int> pre_w(n, 0);
	pre_w[0] = s[0] == '_';
	for (int i = 1; i < n; i++) {
		pre_w[i] = pre_w[i - 1] + (s[i] == '_');
	}
	auto pre = [&] (const std::vector <int>& pre, int l, int r) -> int {
		return pre[r] - (l ? pre[l - 1] : 0);
	};
	auto put = [&] (int i, int j) -> bool {
		if (i + c[j] > n) {
			return false;
		}
		if (pre(pre_w, i, i + c[j] - 1)) {
			return false;
		}
		if (i + c[j] < n && s[i + c[j]] == 'X') {
			return false;
		}
		return true;
	};
	auto f = [&] (auto&& self, int i, int j) -> bool {
		if (i >= n) {
			return j == k;
		}
		if (dp[i][j] != -1) {
			return dp[i][j];
		}
		bool ok = false;
		if (j < k && put(i, j)) {
			if (self(self, i + c[j] + 1, j + 1)) {
				ok = true;
				start_black[i] = std::max(start_black[i], c[j]);
				if (i + c[j] < n) {
					start_white[i + c[j]] = std::max(start_white[i + c[j]], 1);
				}
			}
		}
		if (s[i] != 'X') {
			if (self(self, i + 1, j)) {
				ok = true;
				start_white[i] = std::max(start_white[i], 1);
			}
		}
		return dp[i][j] = ok;
	};
	f(f, 0, 0);
	int cnt_b = 0, cnt_w = 0;
	std::string ans(n, '$');
	for (int i = 0; i < n; i++) {
		cnt_b = std::max(cnt_b, start_black[i]);
		cnt_w = std::max(cnt_w, start_white[i]);
		if (cnt_b && cnt_w) ans[i] = '?';
		else if (cnt_b) ans[i] = 'X';
		else if (cnt_w) ans[i] = '_';
		else assert(false);
		cnt_b--;
		cnt_w--;
	}
	return ans;
}

Compilation message (stderr)

paint.cpp: In instantiation of 'solve_puzzle(std::string, std::vector<int>)::<lambda(auto:23&&, int, int)> [with auto:23 = solve_puzzle(std::string, std::vector<int>)::<lambda(auto:23&&, int, int)>&]':
paint.cpp:54:12:   required from here
paint.cpp:52:19: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   52 |   return dp[i][j] = ok;

• 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