oj.uz

답안 #871079

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
871079 2023-11-09T20:31:08 Z rainboy Fishing Game (RMI19_fishing) C
100 / 100
 361 ms 98204 KB 
#include <stdio.h>
#include <string.h>

#define N	99
#define MD	1000000007

int dp[N * 3 + 1][N * 3 + 1][N * 3 + 1];

int branch(int ab, int bc, int ca, int a, int upd) {
	int x;

	x = 0;
	if (a == 0) {
		if (ab == 0 && ca == 0)
			x = branch(ab, bc, ca, 1, upd);
		else {
			if (ab > 0)
				x = (x + (long long) branch(ab - 1, bc, ca, 1, 1) * ab) % MD;
			if (ca > 0)
				x = (x + (long long) branch(ab, bc + 1, ca - 1, 1, upd) * ca) % MD;
		}
	} else if (a == 1) {
		if (bc == 0 && ab == 0)
			x = branch(ab, bc, ca, 2, upd);
		else {
			if (bc > 0)
				x = (x + (long long) branch(ab, bc - 1, ca, 2, 1) * bc) % MD;
			if (ab > 0)
				x = (x + (long long) branch(ab - 1, bc, ca + 1, 2, upd) * ab) % MD;
		}
	} else if (a == 2) {
		if (ca == 0 && bc == 0)
			x = branch(ab, bc, ca, 3, upd);
		else {
			if (ca > 0)
				x = (x + (long long) branch(ab, bc, ca - 1, 3, 1) * ca) % MD;
			if (bc > 0)
				x = (x + (long long) branch(ab + 1, bc - 1, ca, 3, upd) * bc) % MD;
		}
	} else
		x = upd ? dp[ab][bc][ca] : 0;
	return x;
}

int main() {
	static int aa[N * 3], bb[N * 3];
	int t, n, i, s, ab, bc, ca, a, c;

	scanf("%d%d", &n, &t);
	dp[0][0][0] = 1;
	for (s = 1; s <= n * 3; s++)
		for (ab = 0; ab <= s; ab++)
			for (bc = 0; ab + bc <= s; bc++) {
				ca = s - ab - bc;
				dp[ab][bc][ca] = branch(ab, bc, ca, 0, 0);
			}
	while (t--) {
		memset(aa, -1, n * 3 * sizeof *aa), memset(bb, -1, n * 3 * sizeof *bb);
		for (a = 0; a < 3; a++)
			for (i = 0; i < n * 2; i++) {
				scanf("%d", &c), c--;
				if (aa[c] == -1)
					aa[c] = a;
				else
					bb[c] = a;
			}
		ab = bc = ca = 0;
		for (c = 0; c < n * 3; c++)
			if (aa[c] == 0 && bb[c] == 1)
				ab++;
			else if (aa[c] == 1 && bb[c] == 2)
				bc++;
			else if (aa[c] == 0 && bb[c] == 2)
				ca++;
		printf("%d\n", dp[ab][bc][ca]);
	}
	return 0;
}

Compilation message

fishing.c: In function 'main':
fishing.c:49:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |  scanf("%d%d", &n, &t);
      |  ^~~~~~~~~~~~~~~~~~~~~
fishing.c:61:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     scanf("%d", &c), c--;
      |     ^~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 4 ms 10588 KB Output is correct
4 Correct 7 ms 21084 KB Output is correct
5 Correct 71 ms 52544 KB Output is correct
6 Correct 90 ms 62528 KB Output is correct
7 Correct 132 ms 75092 KB Output is correct
8 Correct 192 ms 85396 KB Output is correct
9 Correct 276 ms 95760 KB Output is correct
10 Correct 361 ms 98204 KB Output is correct