Submission #789163

#	Time	Username	Problem	Language	Result	Execution time	Memory
789163		Sohsoh84	Paint By Numbers (IOI16_paint)	C++17	100 / 100	342 ms	133400 KiB

paint

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

using namespace std;

#define all(x)		(x).begin(),(x).end()
#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;

const int MAXN = 3e5 + 10;
const int MAXK = 100 + 10;

long long n, k, B[MAXN];
bool dp[MAXN][MAXK][2], dp2[MAXN][MAXK][2], W[MAXN];

inline void calc(string s, vector<int> c) {
	s.insert(s.begin(), '#');
	c.insert(c.begin(), 0);

	int max_black = 0;
	dp[0][0][0] = true;
	for (int i = 1; i <= n; i++) {
		bool poss_black = (s[i] != '_');
		bool poss_white = (s[i] != 'X');

		max_black = (poss_black ? max_black + 1 : 0);
		for (int j = 0; j <= k; j++) {
			dp[i][j][0] = ((dp[i - 1][j][0] || dp[i - 1][j][1]) && poss_white);
			if (j && i >= c[j] && max_black >= c[j]) dp[i][j][1] = dp[i - c[j]][j - 1][0];
		}
	}
}

string solve_puzzle(string s, vector<int> c) {
	n = s.size();
	k = c.size();	

	memset(dp, 0, sizeof dp);
	memset(dp2, 0, sizeof dp2);
	memset(B, 0, sizeof B);
	memset(W, 0, sizeof W);

	calc(s, c);
	reverse(all(s));
	swap(dp, dp2);
	reverse(all(c));

	calc(s, c);	
	reverse(all(s));
	swap(dp, dp2);
	reverse(all(c));
	
	c.insert(c.begin(), 0);

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= k; j++) {
			W[i] |= (dp[i][j][0] && dp2[n - i + 1][k - j][0]);
			if (j && dp[i][j][1] && dp2[n - i][k - j][0])
				B[i - c[j] + 1]++, B[i + 1]--;
		}
	}

	for (int i = 1; i <= n; i++)
		B[i] += B[i - 1];

	string ans = "";
	for (int i = 1; i <= n; i++) {
		if (B[i] && W[i]) ans.push_back('?');
		else if (B[i]) ans.push_back('X');
		else if (W[i]) ans.push_back('_');
		else ans.push_back('?');
	}

	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