Submission #405665

#	Time	Username	Problem	Language	Result	Execution time	Memory
405665		rainboy	Paint By Numbers (IOI16_paint)	C11	80 / 100	2071 ms	2336 KiB

paint

#include "paint_c.h"
#include <string.h>

#define N	200000
#define K	100

int solve(char *aa, int *ll, int n, int k) {
	static int dp[N + 1][K + 1], pp[N];
	int h, i;

	for (i = 0; i < n; i++)
		pp[i] = aa[i] == '_' ? i : (i == 0 ? -1 : pp[i - 1]);
	for (i = 0; i <= n; i++)
		memset(dp[i], 0, (k + 1) * sizeof *dp[i]);
	dp[0][0] = 1;
	for (i = 1; i <= n; i++)
		for (h = 0; h <= k; h++) {
			int l = h == 0 ? -1 : ll[h - 1];

			dp[i][h] = aa[i - 1] != 'X' && dp[i - 1][h] || h > 0 && pp[i - 1] < i - l && (i == l ? h == 1 : aa[i - 1 - l] != 'X' && dp[i - 1 - l][h - 1]);
		}
	return dp[n][k];
}

void solve_puzzle(int n, char *aa, int k, int *ll, char *cc) {
	int i;

	for (i = 0; i < n; i++)
		cc[i] = aa[i] == '.' ? '?' : aa[i];
	for (i = 0; i < n; i++)
		if (cc[i] == '?') {
			int can_w, can_b;

			aa[i] = '_', can_w = solve(aa, ll, n, k);
			aa[i] = 'X', can_b = solve(aa, ll, n, k);
			aa[i] = '.';
			if (!can_w)
				cc[i] = 'X';
			else if (!can_b)
				cc[i] = '_';
		}
}

Compilation message (stderr)

paint.c: In function 'solve':
paint.c:20:32: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   20 |    dp[i][h] = aa[i - 1] != 'X' && dp[i - 1][h] || h > 0 && pp[i - 1] < i - l && (i == l ? h == 1 : aa[i - 1 - l] != 'X' && dp[i - 1 - l][h - 1]);
      |               ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~

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