Submission #766026

#	Time	Username	Problem	Language	Result	Execution time	Memory
766026		SanguineChameleon	Paint By Numbers (IOI16_paint)	C++17	100 / 100	175 ms	50960 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 20;
const int maxk = 1e2 + 20;
char a[maxn];
int len[maxk];
int cnt[maxn];
int can[maxn][2];
bool pref[maxn][maxk];
bool suf[maxn][maxk];

string solve_puzzle(string s, vector<int> c) {
	int n = s.size();
	int k = c.size();
	for (int i = 1; i <= n; i++) {
		a[i] = s[i - 1];
	}
	for (int i = 1; i <= k; i++) {
		len[i] = c[i - 1];
	}
	for (int i = 1; i <= n; i++) {
		cnt[i] = cnt[i - 1] + (a[i] == '_');
	}
	pref[0][0] = true;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= k; j++) {
			if (a[i] != 'X') {
				pref[i][j] |= pref[i - 1][j];
			}
			if (j >= 1 && a[i] != '_' && i >= (len[j] + (j > 1)) && cnt[i] == cnt[i - len[j]] && a[i - len[j]] != 'X') {
				pref[i][j] |= pref[i - len[j] - (j > 1)][j - 1];
			}
		}
	}
	suf[n + 1][k + 1] = true;
	for (int i = n; i >= 1; i--) {
		for (int j = 1; j <= k + 1; j++) {
			if (a[i] != 'X') {
				suf[i][j] |= suf[i + 1][j];
			}
			if (j <= k && a[i] != '_' && (i + len[j] + (j < k)) <= n + 1 && cnt[i + len[j] - 1] == cnt[i - 1] && a[i + len[j]] != 'X') {
				suf[i][j] |= suf[i + len[j] + (j < k)][j + 1];
				if (suf[i + len[j] + (j < k)][j + 1] && a[i - 1] != 'X' && i >= (1 + (j > 1)) && pref[i - 1 - (j > 1)][j - 1]) {
					can[i][1]++;
					can[i + len[j]][1]--;
				}
			}
		}
	}
	string res;
	for (int i = 1; i <= n; i++) {
		can[i][1] += can[i - 1][1];
		if (a[i] != 'X') {
			for (int j = 0; j <= k; j++) {
				if (pref[i - 1][j] && suf[i + 1][j + 1]) {
					can[i][0]++;
					break;
				}
			}
		}
		if (can[i][0] && !can[i][1]) {
			res += "_";
		}
		else if (can[i][1] && !can[i][0]) {
			res += "X";
		}
		else {
			res += "?";
		}
	}
	return res;
}

• 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