Submission #832364

#	Time	Username	Problem	Language	Result	Execution time	Memory
832364		happypotato	Paint By Numbers (IOI16_paint)	C++17	100 / 100	156 ms	82688 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back

const int mxN = 2e5 + 10;
bool dp[2][mxN][102][2]; // dp[pre/suf][pos][kth segment][X/_]
int checkps[mxN];
int cross[mxN];
string solve_puzzle(string s, vector<int> c) {
	int n = s.length();
	s = '!' + s + '!';
	int k = c.size();
	c.insert(c.begin(), -1);
	
	checkps[0] = 0;
	for (int i = 1; i <= n; i++) {
		checkps[i] = checkps[i - 1] + (s[i] == '_');
	}

	dp[0][0][0][0] = dp[0][0][0][1] = 1;
	// sweep forward
	for (int i = 1; i <= n; i++) {
		dp[0][i][0][0] = 0; dp[0][i][0][1] = (dp[0][i - 1][0][1] && (s[i] != 'X'));
		for (int j = 1; j <= k; j++) {
			int prev = i - c[j];
			if (prev < 0 || checkps[i] - checkps[prev] != 0) {
				dp[0][i][j][0] = 0;
			} else {
				dp[0][i][j][0] = dp[0][prev][j - 1][1];
			}
			dp[0][i][j][1] = ((dp[0][i - 1][j][0] | dp[0][i - 1][j][1]) && (s[i] != 'X'));
		}
	}
	// sweep backward
	dp[1][n + 1][k + 1][0] = dp[1][n + 1][k + 1][1] = 1;
	for (int i = n; i >= 1; i--) {
		dp[1][i][k + 1][0] = 0; dp[1][i][k + 1][1] = (dp[1][i + 1][k + 1][1] && (s[i] != 'X'));
		for (int j = k; j >= 1; j--) {
			int prev = i + c[j];
			if (prev > n + 1 || checkps[prev - 1] - checkps[i - 1] != 0) {
				dp[1][i][j][0] = 0;
			} else {
				dp[1][i][j][0] = dp[1][prev][j + 1][1];
			}
			dp[1][i][j][1] = ((dp[1][i + 1][j][0] | dp[1][i + 1][j][1]) && (s[i] != 'X'));
		}
	}
	// for (int i = 1; i <= n; i++) {
	// 	for (int j = 0; j <= k + 1; j++) {
	// 		cout << dp[0][i][j][0] << dp[0][i][j][1] << ' ';
	// 	}
	// 	cout << endl;
	// }
	// cout << endl;
	// for (int i = 1; i <= n; i++) {
	// 	for (int j = 0; j <= k + 1; j++) {
	// 		cout << dp[1][i][j][0] << dp[1][i][j][1] << ' ';
	// 	}
	// 	cout << endl;
	// }

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			if (i + c[j] - 1 > n) continue;
			if (!dp[0][i - 1][j - 1][1] || !dp[1][i + c[j]][j + 1][1]) continue;
			if (checkps[i + c[j] - 1] - checkps[i - 1] != 0) continue;
			// [i, i + c[j]) can be 'X'
			// cerr << i << ' ' << j << ' ' << c[j] << endl;
			cross[i]++; cross[i + c[j]]--;
		}
	}

	string ans = s;
	for (int i = 1; i <= n; i++) {
		int msk = 0;
		// check for 'X'
		cross[i] += cross[i - 1];
		if (cross[i] > 0) msk |= 1;
		// check for '_'
		for (int j = 0; j <= k; j++) {
			if (dp[0][i][j][1] && dp[1][i][j + 1][1]) {
				msk |= 2;
				break;
			}
		}
		// cerr << i << ": " << msk << endl;
		if (ans[i] != '.') continue;
		if (msk == 0) throw runtime_error("invalid solution?");
		if (msk == 1) ans[i] = 'X';
		if (msk == 2) ans[i] = '_';
		if (msk == 3) ans[i] = '?';
	}
	ans.erase(ans.begin());
	ans.erase(--ans.end());
	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