Submission #92614

#	Time	Username	Problem	Language	Result	Execution time	Memory
92614		turbat	Paint By Numbers (IOI16_paint)	C++14	0 / 100	67 ms	82552 KiB

paint

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

int n, t, ok, now, cnt[N], l[105], r[105], dp[N][105];
string ans, st;
vector <int> ve;

void rec(int x, int idx){
	if (dp[x][idx] != -1) return;
	if (!idx){
		if (x + 1 >= ve[0] && !cnt[x - ve[0]] && (idx != t - 1 || !(cnt[n - 1] - cnt[x])) ) {
			dp[x][idx] = 1;
			r[idx] = max(r[idx], x);
			l[idx] = min(l[idx], x);
		}
		else dp[x][idx] = 0;
		return;
	}
	if (st[x - ve[idx]] != 'X')
		rec(x - ve[idx] - 1, idx - 1);
	else dp[x - ve[idx]][idx] = 0;
	if (x + 1 >= ve[idx] && dp[x - ve[idx]][idx - 1]&& !(cnt[x] - cnt[x - ve[idx]]) && (idx != t - 1 || !(cnt[n - 1] - cnt[x])) ){
		if (st[x + 1] != 'X') dp[x + 1][idx] = 1;
		r[idx] = max(r[idx], x);
		l[idx] = min(l[idx], x);
		rec(x - 1, idx);
	}
	else dp[x][idx] = 0;
}

string solve_puzzle(string s, vector<int> c) {
	st = s;
	ve = c;
	n = s.size();
	t = c.size();
	for (int i = 0;i < t;i++)
		l[i] = n;
	now = 0;
	memset(dp, -1, sizeof dp);
	for (int i = 0;i < n;i++){
		cnt[i] = cnt[i - 1] + s[i - 1] == '_';
		ans += '?';
	}
	for (int i = n - 1;i > 0;i--)
		rec(i, t - 1);
	for (int i = 0;i <= l[0] - ve[0];i++)
		ans[i] = '_';
	for (int i = r[t - 1] + 1; i < n;i++)
		ans[i] = '_';
	for (int i = 0;i < t;i++){
		if (i)
			for (int j = r[i - 1] + 1;j <= l[i] - ve[i];j++)
				ans[j] = '_';
		for (int j = r[i] - ve[i] + 1;j <= l[i];j++)
			ans[j] = 'X';
	}
	return ans;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 3
• Subtask 3: 0 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10