Submission #275506

#	Time	Username	Problem	Language	Result	Execution time	Memory
275506		ggooroo	Paint By Numbers (IOI16_paint)	C++14	59 / 100	125 ms	164880 KiB

paint

#include "paint.h"
#include <cstdlib>
#include <vector>
#include <cstdio>
#include <iostream>
#include <cstring>
#define N 200005
using namespace std;

int n, m, c[N], v[N][105][2], ans[N][2], ss[N], cnt[N], mx[N];
string a;

int g(int p) {
	if (p < 0) return 0;
	return cnt[p];
}

int f(int p, int q, int z) {
	int t, ch = 0, cch = 0, pl;
	if (p >= n) {
		if (q == m) return 1;
		return 0;
	}
	if (v[p][q][z] != -1) return v[p][q][z];
	pl = c[q + 1];
	if (q < m && p + pl - 1 < n && g(p + pl - 1) - g(p - 1) == 0 && z == 0 && a[p + pl] != 'X') {
		t = f(p + pl, q + 1, 1);
		if (t == 1) {
			ans[p][0] = 1;
			cch = 1;
		}
	}
	t = f(p + 1, q, 0);
	if (t == 1) {
		ans[p][1] = 1;
		ch = 1;
	}
	if (cch) {
		mx[p] = max(mx[p], p + pl - 1);
	}
//	if ((a[p] == '.' || a[p] == 'X')) {
//		if (q + 1 < ss[w]) t = f(p + 1, q + 1, w, 0);
//		else t = f(p + 1, q + 1, w + 1, 1);
//		if (t == 1) {
//			ans[p][0] = 1;
//			ch = 1;
//		}
//	}
//	if ((a[p] == '.' || a[p] == '_') && !(z == 0 && q > ss[w - 1] && q < ss[w])) {
//		t = f(p + 1, q, w);
//		if (t == 1) {
//			ans[p][1] = 1;
//			ch = 1;
//		}
//	}
	return v[p][q][z] = (ch | cch);
}

std::string solve_puzzle(std::string s, std::vector<int> cc) {
	int i, la;
	a = s;
	n = a.size();
	if (a[0] == '_') cnt[0] = 1;
	else cnt[0] = 0;
	for (i = 1; i < n; i++) cnt[i] = cnt[i - 1] + (a[i] == '_');
	cnt[n] = cnt[n - 1];
	m = cc.size();
	for (i = 0; i < m; i++) {
		c[i + 1] = cc[i];
	}
	for (i = 1; i <= m; i++) ss[i] = ss[i - 1] + c[i];
	memset(v, -1, sizeof(v));
	f(0, 0, 0);
	la = -1;
	bool vb, vw;
	for (i = 0; i < n; i++) {
		vb = vw = 0;
		if (ans[i][0]) la = max(la, mx[i]);
		if (ans[i][0]) vb = 1;
		if (la != -1 && i <= la) vb = 1;
		if (ans[i][1]) vw = 1;
		if (vb + vw == 2) {
			a[i] = '?';
		} else if (vb + vw == 1) {
			if (vb == 1) a[i] = 'X';
			else a[i] = '_';
		} else a[i] = '?';
	}
    return a;
}

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