Submission #290093

#	Time	Username	Problem	Language	Result	Execution time	Memory
290093		amoo_safar	Paint By Numbers (IOI16_paint)	C++17	100 / 100	423 ms	45028 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>

using namespace std;

typedef string str;

const int N = 2e5 + 5;
const int K = 1e2 + 5;

bool dp[N][K];
bool rdp[N][K];
int ps[N];
int B[N], W[N];

str solve_puzzle(str s, vector<int> C){
	int k = (int) C.size();
	s = "_" + s + "_";
	int n = (int) s.size();

	ps[0] = 0;
	for(int i = 1; i <= n; i++) ps[i] = ps[i - 1] + (s[i - 1] == '_');

	memset(dp, 0, sizeof dp);
	dp[0][0] = true;
	for(int i = 1; i < n; i++){
		if(s[i] == 'X') continue;
		for(int j = 0; j <= k; j++){
			dp[i][j] = dp[i - 1][j];
			if(j > 0 && C[j - 1] < i && ps[i] == ps[i - C[j - 1]])
				dp[i][j] |= dp[i - C[j - 1] - 1][j - 1];
		}
	}

	memset(rdp, 0, sizeof rdp);
	rdp[n - 1][0] = true;
	for(int i = n - 2; i >= 0; i--){
		if(s[i] == 'X') continue;
		for(int j = 0; j <= k; j++){
			rdp[i][j] = rdp[i + 1][j];
			if(j > 0 && C[k - j] < n - 1 - i && ps[i + 1] == ps[i + 1 + C[k - j]])
				rdp[i][j] |= rdp[i + C[k - j] + 1][j - 1];
		}
	}

	for(int i = 0; i < n; i++){
		for(int j = 0; j <= k; j++)
			if(dp[i][j] && rdp[i][k - j])
				W[i] = 1;
	}
	for(int i = 0; i < k; i++){
		for(int st = 1; st + C[i] < n; st ++){
			if(ps[st] != ps[st + C[i]]) continue;
			if(dp[st - 1][i] && rdp[st + C[i]][k - i - 1])
				B[st] ++, B[st + C[i]] --;
		}
	}
	for(int i = 1; i < n; i++) B[i] += B[i - 1];

	str res = "";
	for(int i = 1; i < n - 1; i++){
		B[i] = min(B[i], 1);
		assert(W[i] + B[i] >= 1);
		if(W[i] == 1 && B[i] == 1) res += "?";
		else if(W[i] == 1) res += "_";
		else res += "X";
	}
	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