Submission #116344

#	Time	Username	Problem	Language	Result	Execution time	Memory
116344		valentin_imbach	Paint By Numbers (IOI16_paint)	C++14	59 / 100	6 ms	384 KiB

paint

#include "paint.h"
#include <cstdlib>
#include <iostream>

using namespace std;

int n, k;
vector<int> l;
vector<int> r;
vector<int> last;
vector<int> nexxt;

string solve_puzzle(string s, vector<int> c) {

	n = s.size();
	k = c.size();
	l = vector<int>(k);
	r = vector<int>(k);
	last = vector<int>(n);
	nexxt = vector<int>(n);

	if (s[0] != '_') {
		last[0] = -1;
	}
	if (s[n-1] != '_') {
		nexxt[n-1] = n;
	} else {
		nexxt[n-1] = n-1;
	}
	for (int i = 1; i < n; i++) {
		if (s[i] == '_') {
			last[i] = i;
		} else {
			last[i] = last[i-1];
		}
	}
	for (int i = n-2; i >= 0; i--) {
		if (s[i] == '_') {
			nexxt[i] = i;
		} else {
			nexxt[i] = nexxt[i+1];
		}
	}

	int lindex = 0;
	int rindex = n-1;
	for (int i = 0; i < k; i++) {
		while (true) {
			int fail = -1;
			for (int j = lindex; j < lindex+c[i]; j++) {
				if (s[j] == '_') {
					fail = j;
				}
			}
			if (fail == -1) {
				l[i] = lindex;
				lindex = lindex+c[i]+1;
				break;
			} else {
				lindex = fail+1;
			}
		}
		while (true) {
			int fail = -1;
			for (int j = rindex; j > rindex-c[k-1-i]; j--) {
				if (s[j] == '_') {
					fail = j;
				}
			}
			if (fail == -1) {
				r[k-1-i] = rindex;
				rindex = rindex-c[k-1-i]-1;
				break;
			} else {
				rindex = fail-1;
			}
		}
	}

	/*
	for (int i = 0; i < k; i++) {
		cout << l[i] << " " << r[i] << endl;
	}*/

	string res = "";
	for (int i = 0; i < n; i++) {
		bool cover = false;
		bool free = false;
		for (int j = 0; j < k; j++) {
			int left = max(l[j],last[i]+1);
			int right = min(r[j],nexxt[i]-1);

			/*
			if (i == 3) {
				cout << "- " << left << " " << right << endl;
			}*/

			if (right-left+1 >= c[j]) {
				if (left <= i && i <= right) {
					cover = true;
				}
			}
		}
		for (int j = 0; j < k-1; j++) {
			if (l[j]+c[j] <= i && i <= r[j+1]-c[j+1]) {
				free = true;
			}
		}
		if (l[k-1]+c[k-1] <= i || i <= r[0]-c[0]) {
			free = true;
		}
		if (free && cover) {
			res += '?';
		} else if (free) {
			res += '_';
		} else {
			res += 'X';
		}
	}

    return res;
}

• 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