Submission #115090

#	Time	Username	Problem	Language	Result	Execution time	Memory
115090		E869120	Paint By Numbers (IOI16_paint)	C++14	0 / 100	2 ms	384 KiB

paint

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

int N, K; tuple<int, int, int> pre[200009][109][2]; int t[200009][3];
bool dp[200009][109][2]; char cc[200009];

int ranged(int l, int r, int x) {
	return t[r][x] - t[l - 1][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] == 'X') t[i + 1][0]++;
		if (s[i] == '_') 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];
	}
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= K; j++) {
			for (int k = 0; k < 3; k++) pre[i][j][k] = make_tuple(-1, -1, -1);
		}
	}
	
	dp[0][0][0] = true;
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j <= K; j++) {
			int pres = -1, pre2 = -1;
			if (i >= 1 && ranged(i, i, 0) == 0) {
				if (dp[i - 1][j][0] == true) { pres = j; pre2 = 0; }
				else if (dp[i - 1][j][1] == true) { pres = j; pre2 = 1; }
			}
			if (pres >= 0) {
				pre[i][j][0] = make_tuple(i - 1, pres, pre2); dp[i][j][0] = true;
			}
			pres = -1; pre2 = -1;
			if (j >= 1 && i >= c[j - 1] && ranged(i - c[j - 1] + 1, i, 1) == 0) {
				if (dp[i - c[j - 1]][j - 1][0] == true) { pres = j - 1; pre2 = 0; }
			}
			if (pres >= 0) {
				pre[i][j][1] = make_tuple(i - c[j - 1], pres, pre2); dp[i][j][1] = true;
			}
		}
	}
	for (int i = 1; i <= N; i++) cc[i] = '_';
	
	int cx = N, cy = K, cz = 0; if (dp[N][K][0] == false) cz = 1;
	while (cx >= 1) {
		int v1 = get<0>(pre[cx][cy][cz]), v2 = get<1>(pre[cx][cy][cz]), v3 = get<2>(pre[cx][cy][cz]);
		//cout << cx << " " << cy << " " << cz << " " << v1 << " " << v2 << " " << v3 << endl;
		if (cz == 1) {
			for (int i = v1 + 1; i <= cx; i++) cc[i] = 'X';
		}
		cx = v1; cy = v2; cz = v3;
	}
	
	string str = "";
	for (int i = 1; i <= N; i++) str += cc[i];
	return str;
}

• 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