oj.uz

Submission #719356

# Submission time Handle Problem Language Result Execution time Memory
719356 2023-04-05T20:02:41 Z rainboy parentrises (BOI18_parentrises) C
100 / 100
 102 ms 12436 KB 
#include <stdio.h>
#include <string.h>

#define N	300
#define L	1000000
#define MD	1000000007

int max(int a, int b) { return a > b ? a : b; }

int ans[N + 1];

void init() {
	static int dp[N + 1][N * 2 + 1], dq[N + 1][N * 2 + 1];
	int n, a, a_, b, b_;

	dp[0][0] = 1;
	ans[0] = 1;
	for (n = 1; n <= N; n++) {
		for (a = 0; a <= n; a++)
			memset(dq[a], 0, (n * 2 + 1) * sizeof *dq[a]);
		for (a = 0; a <= n - 1; a++)
			for (b = 0; b <= (n - 1) * 2; b++) {
				int x = dp[a][b];

				a_ = a + 1, b_ = b + 2;
				dq[a_][b_] = (dq[a_][b_] + x) % MD;
				if (b > 0) {
					a_ = max(a - 2, 0), b_ = b - 1;
					dq[a_][b_] = (dq[a_][b_] + x) % MD;
				}
			}
		for (a = 0; a <= n; a++)
			memcpy(dp[a], dq[a], (n * 2 + 1) * sizeof *dq[a]);
		for (b = 0; b <= n * 2; b++)
			ans[n] = (ans[n] + dp[0][b]) % MD;
	}
}

int main() {
	int mode, t;

	scanf("%d%d", &mode, &t);
	init();
	while (t--)
		if (mode == 1) {
			static char cc[L + 1];
			static int aa[L + 1], bb[L + 1];
			int l, h, bad, d;

			scanf("%s", cc), l = strlen(cc);
			bad = 0;
			aa[0] = bb[0] = 0;
			for (h = 0; h < l; h++)
				if (cc[h] == '(')
					aa[h + 1] = aa[h] + 1, bb[h + 1] = bb[h] + 2;
				else {
					if (bb[h] == 0) {
						bad = 1;
						break;
					}
					aa[h + 1] = max(aa[h] - 2, 0), bb[h + 1] = bb[h] - 1;
				}
			if (bad || aa[l] > 0)
				printf("impossible\n");
			else {
				d = 0;
				for (h = l - 1; h >= 0; h--)
					if (cc[h] == '(') {
						if (d - 1 <= bb[h])
							cc[h] = d % 2 == 0 ? 'B' : 'R', d--;
						else
							cc[h] = 'G', d -= 2;
					} else {
						if (d + 1 >= aa[h])
							cc[h] = d % 2 == 0 ? 'R' : 'B', d++;
						else
							cc[h] = 'G', d += 2;
					}
				printf("%s\n", cc);
			}
		} else {
			int n;

			scanf("%d", &n);
			printf("%d\n", ans[n]);
		}
	return 0;
}

Compilation message

parentrises.c: In function 'main':
parentrises.c:42:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |  scanf("%d%d", &mode, &t);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~
parentrises.c:50:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |    scanf("%s", cc), l = strlen(cc);
      |    ^~~~~~~~~~~~~~~
parentrises.c:84:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |    scanf("%d", &n);
      |    ^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 1644 KB Output is correct
2 Correct 78 ms 1640 KB Output is correct
3 Correct 78 ms 1604 KB Output is correct
4 Correct 92 ms 1644 KB Output is correct
5 Correct 78 ms 1644 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 1700 KB Output is correct
2 Correct 77 ms 1676 KB Output is correct
3 Correct 78 ms 1624 KB Output is correct
4 Correct 78 ms 1660 KB Output is correct
5 Correct 78 ms 1612 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 1700 KB Output is correct
2 Correct 77 ms 1676 KB Output is correct
3 Correct 78 ms 1624 KB Output is correct
4 Correct 78 ms 1660 KB Output is correct
5 Correct 78 ms 1612 KB Output is correct
6 Correct 77 ms 1664 KB Output is correct
7 Correct 81 ms 1656 KB Output is correct
8 Correct 80 ms 1692 KB Output is correct
9 Correct 81 ms 1600 KB Output is correct
10 Correct 78 ms 1676 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 1700 KB Output is correct
2 Correct 77 ms 1676 KB Output is correct
3 Correct 78 ms 1624 KB Output is correct
4 Correct 78 ms 1660 KB Output is correct
5 Correct 78 ms 1612 KB Output is correct
6 Correct 77 ms 1664 KB Output is correct
7 Correct 81 ms 1656 KB Output is correct
8 Correct 80 ms 1692 KB Output is correct
9 Correct 81 ms 1600 KB Output is correct
10 Correct 78 ms 1676 KB Output is correct
11 Correct 79 ms 1744 KB Output is correct
12 Correct 82 ms 1740 KB Output is correct
13 Correct 85 ms 1624 KB Output is correct
14 Correct 79 ms 1740 KB Output is correct
15 Correct 79 ms 1784 KB Output is correct
16 Correct 81 ms 1868 KB Output is correct
17 Correct 82 ms 2744 KB Output is correct
18 Correct 78 ms 1848 KB Output is correct
19 Correct 79 ms 2284 KB Output is correct
20 Correct 81 ms 2784 KB Output is correct
21 Correct 91 ms 3472 KB Output is correct
22 Correct 102 ms 12436 KB Output is correct
23 Correct 92 ms 4260 KB Output is correct
24 Correct 94 ms 7756 KB Output is correct
25 Correct 96 ms 12360 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 1688 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 1688 KB Output is correct
2 Correct 77 ms 1648 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 1688 KB Output is correct
2 Correct 77 ms 1648 KB Output is correct
3 Correct 81 ms 1668 KB Output is correct