Submission #119071

#	Time	Username	Problem	Language	Result	Execution time	Memory
119071		turbat	Paint By Numbers (IOI16_paint)	C++14	90 / 100	191 ms	177600 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define N 200005
 
int n, k, cnt[N], can[N], dp[N][105], paint[N];
vector <int> c;
string s, ans;
 
int solve(int idx, int col){
	if (!col && !idx) return 1;
	if (idx < 0) return 0;
	if (dp[idx][col] != -1) return dp[idx][col];
	dp[idx][col] = 0;
	// cout << idx << ' '<< col << endl;
	if (s[idx] != 'X' && solve(idx - 1, col)) can[idx] = dp[idx][col] = 1;
	if (col && cnt[idx] - cnt[idx - c[col - 1]] == 0 && s[idx - c[col - 1]] != 'X')
		if ((col == 1 && !(idx - c[col - 1])) || solve(idx - c[col - 1] - 1, col - 1)){
			dp[idx][col] = 1;
			paint[idx]++;
			paint[idx - c[col - 1]]--;
			can[idx - c[col - 1]] = 1;
		}
	// cout << idx << ' '<< col << ' '<< dp[idx][col]<< endl;
	return dp[idx][col];
}
string solve_puzzle(string ss, vector<int> cc) {
	s = '_' + ss;
	c = cc;
	n = s.size();
	k = c.size();
	for (int i = 1;i < n;i++){
		if (s[i] == '_') cnt[i]++;
		cnt[i] += cnt[i - 1];
	}
	memset(dp, -1, sizeof dp);
	solve(n - 1, k);
	for (int i = n - 1;i > 0;i--) paint[i] += paint[i + 1];
	for (int i = 1;i < n;i++){
		int d = 0;
		if (paint[i]) d += 1;
		if (can[i]) d += 2;
		if (!d) ans += 'G';
		if (d == 1) ans += 'X';
		if (d == 2) ans += '_';
		if (d == 3) 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