Submission #115102

#	Time	Username	Problem	Language	Result	Execution time	Memory
115102		E869120	Paint By Numbers (IOI16_paint)	C++14	100 / 100	427 ms	90796 KiB

paint

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

int N, K, t[200009][3], v1[200009], v2[200009];
bool dpl[200009][109][2], dpr[200009][109][2];

int ranged(int l, int r, int x) {
	return t[r + 1][x] - t[l][x];
}

string solve_puzzle(string s, vector<int> c) {
	N = s.size(); K = c.size();
	for (int i = 0; i < N; i++) {
		if (s[i] == '_') t[i + 1][0]++;
		if (s[i] == 'X') t[i + 1][1]++;
		if (s[i] == '?') t[i + 1][2]++;
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < 3; j++) t[i][j] += t[i - 1][j];
	}
	
	dpl[0][0][0] = true;
	for (int  i = 1; i <= N; i++) {
		for (int j = 0; j <= K; j++) {
			if (dpl[i - 1][j][0] == true && s[i - 1] != 'X') dpl[i][j][0] = true;
			if (dpl[i - 1][j][1] == true && s[i - 1] != 'X') dpl[i][j][0] = true;
			if (j >= 0 && i >= c[j - 1] && dpl[i - c[j - 1]][j - 1][0] == true && ranged(i - c[j - 1], i - 1, 0) == 0) dpl[i][j][1] = true;
		}
	}
	
	dpr[N][K][0] = true;
	for (int i = N - 1; i >= 0; i--) {
		for (int j = 0; j <= K; j++) {
			if (dpr[i + 1][j][0] == true && s[i] != 'X') dpr[i][j][0] = true;
			if (dpr[i + 1][j][1] == true && s[i] != 'X') dpr[i][j][0] = true;
			if (j < K && i + c[j] <= N && dpr[i + c[j]][j + 1][0] == true && ranged(i, i + c[j] - 1, 0) == 0) dpr[i][j][1] = true;
		}
	}
	
	for (int i = 0; i < N; i++) {
		bool p1 = false;
		for (int j = 0; j <= K; j++) {
			if (s[i] == 'X') continue;
			if ((dpl[i][j][0] == false && dpl[i][j][1] == false) || dpl[i + 1][j][0] == false) continue;
			if ((dpr[i + 1][j][0] == false && dpr[i + 1][j][1] == false) || dpr[i][j][0] == false) continue;
			p1 = true; break;
		}
		for (int j = 0; j < K; j++) {
			if (s[i] == '_') continue;
			if (i + 1 < c[j] || dpl[i - c[j] + 1][j][0] == false || dpl[i + 1][j + 1][1] == false) continue;
			if (i + 1 < c[j] || dpr[i - c[j] + 1][j][1] == false || dpr[i + 1][j + 1][0] == false) continue;
			v2[i - c[j] + 1] += 1;
			v2[i + 1] -= 1;
		}
		if (p1 == true) v1[i] = 1;
	}
	for (int i = 1; i <= N + 1; i++) v2[i] += v2[i - 1];
	
	string str = "";
	for (int i = 0; i < N; i++) {
		if (v1[i] >= 1 && v2[i] >= 1) str += '?';
		if (v1[i] >= 1 && v2[i] == 0) str += '_';
		if (v1[i] == 0 && v2[i] >= 1) str += 'X';
		if (v1[i] == 0 && v2[i] == 0) str += 'A';
	}
	return str;
}

• 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: 10 / 10