Submission #722676

#	Time	Username	Problem	Language	Result	Execution time	Memory
722676		rainboy	Human Error (CCO19_day1problem1)	C11	25 / 25	29 ms	4180 KiB

Main

#include <stdio.h>

#define NM	13
#define P	1594323

int min(int a, int b) { return a < b ? a : b; }

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int di[] = { -1, 1, 0, 0 };
int dj[] = { 0, 0, -1, 1 };

int pp3[NM + 1];

void init() {
	int i;

	pp3[0] = 1;
	for (i = 1; i <= NM; i++)
		pp3[i] = pp3[i - 1] * 3;
}

char digit(int b, int h) {
	return b / pp3[h] % 3;
}

double dp[P]; char visited[P]; int n, m, k1, k2;

void sort(double *aa, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r;
		double a = aa[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (aa[j] == a)
				j++;
			else if (aa[j] < a) {
				tmp = aa[i], aa[i] = aa[j], aa[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = aa[j], aa[j] = aa[k], aa[k] = tmp;
			}
		sort(aa, l, i);
		l = k;
	}
}

double solve(int b, int turn) {
	static double aa[NM * 4];
	int k, g, h, h_, i, i_, j, j_, d;

	if (!visited[b]) {
		visited[b] = 1;
		for (i = 0; i < n; i++)
			for (j = 0; j < m; j++) {
				h = i * m + j;
				if (digit(b, h) == turn)
					for (g = 0; g < 4; g++) {
						i_ = i + di[g], j_ = j + dj[g], h_ = i_ * m + j_;
						if (i_ >= 0 && i_ < n && j_ >= 0 && j_ < m && (d = digit(b, h_)) != 0)
							solve(b - turn * pp3[h] + (turn - d) * pp3[h_], turn ^ 3);
					}
			}
		k = 0;
		for (i = 0; i < n; i++)
			for (j = 0; j < m; j++) {
				h = i * m + j;
				if (digit(b, h) == turn)
					for (g = 0; g < 4; g++) {
						i_ = i + di[g], j_ = j + dj[g], h_ = i_ * m + j_;
						if (i_ >= 0 && i_ < n && j_ >= 0 && j_ < m && (d = digit(b, h_)) != 0)
							aa[k++] = solve(b - turn * pp3[h] + (turn - d) * pp3[h_], turn ^ 3);
					}
			}
		sort(aa, 0, k);
		k = min(k, turn == 1 ? k1 : k2);
		dp[b] = 0;
		if (k != 0) {
			for (g = 0; g < k; g++)
				dp[b] += 1 - aa[g];
			dp[b] /= k;
		}
	}
	return dp[b];
}

int main() {
	static char cc[NM + 1];
	int i, j, h, b;

	init();
	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		scanf("%s", cc + i * m);
	scanf("%d%d", &k1, &k2);
	b = 0;
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++) {
			h = i * m + j;
			if (cc[h] == 'J')
				b += pp3[h];
			else if (cc[h] == 'D')
				b += pp3[h] * 2;
		}
	printf("%.3f\n", solve(b, 1));
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:97:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:99:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |   scanf("%s", cc + i * m);
      |   ^~~~~~~~~~~~~~~~~~~~~~~
Main.c:100:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |  scanf("%d%d", &k1, &k2);
      |  ^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 25 / 25