Submission #274957

#	Time	Username	Problem	Language	Result	Execution time	Memory
274957		ggooroo	Paint By Numbers (IOI16_paint)	C++14	90 / 100	196 ms	197880 KiB

paint

#include "paint.h"

#include <cstdlib>
#include <vector>
#include <cstdio>
#include <iostream>
#include <cstring>
#define N 5005
using namespace std;

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

int f(int p, int q, int w, int z) {
	int t, ch = 0;
	if (v[p][q][z] != -1) return v[p][q][z];
	if (p == 7 && q == 3 && z == 0) {
		t = 0;
	}
	if (p == n) {
		if (w == m + 1) return 1;
		return 0;
	}
	if (z == 0 && (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, 0);
		if (t == 1) {
			ans[p][1] = 1;
			ch = 1;
		}
	}
	return v[p][q][z] = ch;
}

std::string solve_puzzle(std::string s, std::vector<int> cc) {
	int i;
	a = s;
	n = a.size();
	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, 1, 0);
	for (i = 0;i < n; i++) {
		if (ans[i][0] + ans[i][1] == 2) {
			a[i] = '?';
		} else if (ans[i][0] + ans[i][1] == 1) {
			if (ans[i][0] == 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: 21 / 21
• Subtask 6: 10 / 10
• Subtask 7: 0 / 10