Submission #365277

#	Time	Username	Problem	Language	Result	Execution time	Memory
365277		Sparky_09	Paint By Numbers (IOI16_paint)	C++17	90 / 100	2078 ms	31840 KiB

paint

#include "paint.h"
#include "bits/stdc++.h"
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define trav(a, x) for(auto& a : x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpi;

const int N = 200005;
const int M = 105;

char s[N];
int n, m, c[N], sum[N], canblack[N], canwhite[N];
bool dp[N][M], ds[N][M];

inline bool nowhite(int l, int r) {
	return sum[r] - sum[l - 1] == 0;
}

inline bool place1(int i, int j) {
	if (!j) return 0;
	if (i - c[j] - 1 < 0) return 0;
	return dp[i - c[j] - 1][j - 1] && nowhite(i - c[j], i - 1);
}

inline bool place2(int i, int j) {
	if (!j) return 0;
	if (i + c[j] + 1 > n + 1) return 0;
	return ds[i + c[j] + 1][j + 1] && nowhite(i + 1, i + c[j]);
}

string solve_puzzle(string ss, vector<int> cc) {
	n = ss.length(), m = cc.size();
	for (int i = 1; i <= n; ++i) {
		s[i] = ss[i - 1];
		sum[i] = sum[i - 1] + (s[i] == '_');
	}
	for (int i = 1; i <= m; ++i) {
		c[i] = cc[i - 1];
	}
	dp[0][0] = 1;
	for (int i = 1; i <= n + 1; ++i) {
		if (s[i] == 'X') continue;
		for (int j = 0; j <= m; ++j) {
			dp[i][j] = dp[i - 1][j] || place1(i, j);
		}	
	}
	ds[n + 1][m + 1] = 1;
	for (int i = n; i >= 0; --i) {
		if (s[i] == 'X') continue;
		for (int j = m + 1; j >= 1; --j) {
			if (!dp[i][j - 1]) continue;
			ds[i][j] = ds[i + 1][j] || place2(i, j);
			canwhite[i] |= ds[i][j];
			if (place2(i, j)) {
				++canblack[i + 1];
				--canblack[i + c[j] + 1];
			}
		}
	}
	string ans; ans.clear();
	for (int i = 1; i <= n; ++i) {
		canblack[i] += canblack[i - 1];
		if (!canwhite[i]) ans = ans + 'X';
		else if (!canblack[i]) ans = ans + '_';
		else ans = 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: 0 / 10