Submission #258550

#	Time	Username	Problem	Language	Result	Execution time	Memory
258550		ChrisT	Paint By Numbers (IOI16_paint)	C++17	100 / 100	684 ms	31088 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
string solve_puzzle (string s, vector<int> c) {
	int n = s.length(), k = c.size(); 
	s = 'X' + s + 'X';
	vector<vector<bool>> dp(n+2,vector<bool>(k+1)), dp2(n+2,vector<bool>(k+1));
	vector<int> psa(n+1);
	for (int i = 1; i <= n; i++) psa[i] = psa[i-1] + (s[i] == '_');
	dp[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		if (s[i] != 'X') dp[i][0] = dp[i-1][0];
		if (s[i] != 'X') dp[i][1] = dp[i-1][1];
		if (i >= c[0] && psa[i] == psa[i-c[0]]) dp[i][1] = dp[i][1] | dp[i-c[0]][0];
		for (int j = 2; j <= k; j++) {
			if (s[i] != 'X') dp[i][j] = dp[i-1][j];
			if (i - c[j-1] >= 1 && psa[i] == psa[i-c[j-1]] && s[i-c[j-1]] != 'X') 
				dp[i][j] = dp[i][j] | dp[i-c[j-1]-1][j-1];
		}
	}
	dp2[n+1][0] = 1;
	for (int i = n; i >= 1; i--) {
		if (s[i] != 'X') dp2[i][0] = dp2[i+1][0];
		if (s[i] != 'X') dp2[i][1] = dp2[i+1][1];
		if (i + c[k-1] - 1 <= n && psa[i + c[k-1] - 1] == psa[i-1]) dp2[i][1] = dp2[i][1] | dp2[i+c[k-1]][0];
		for (int j = 2; j <= k; j++) {
			if (s[i] != 'X') dp2[i][j] = dp2[i+1][j];
			if (i + c[k-j] <= n && psa[i+c[k-j]-1] == psa[i-1] && s[i+c[k-j]] != 'X')
				dp2[i][j] = dp2[i][j] | dp2[i+c[k-j]+1][j-1];
		}
	}
	vector<int> diff(n+2);
	for (int j = 1; j <= k; j++) {
		for (int i = 1; i + c[j-1] - 1 <= n; i++) if (psa[i+c[j-1]-1]==psa[i-1]&& (j == 1 || s[i-1] != 'X') && (j == k || s[i + c[j-1]] != 'X') && dp[i-1-(j!=1)][j-1] && dp2[i+c[j-1]+(j!=k)][k-j]){
			diff[i]++; diff[i+c[j-1]]--;
		}
	}
	for (int i = 1; i <= n; i++) {
		diff[i] += diff[i-1];
		bool white = 0, black = diff[i];
		for (int j = 0; j <= k; j++) {
			white |= s[i] != 'X' && dp[i-1][j] && dp2[i+1][k-j];
		}
		assert(white || black);
		s[i] = white && black ? '?' : (white ? '_' : 'X');
	}
	return s.substr(1,n);
}

• 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