Submission #719356

#	Time	Username	Problem	Language	Result	Execution time	Memory
719356		rainboy	parentrises (BOI18_parentrises)	C11	100 / 100	102 ms	12436 KiB

parentrises

#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 (stderr)

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 / 5
• Subtask 2: 11 / 11
• Subtask 3: 6 / 6
• Subtask 4: 28 / 28
• Subtask 5: 6 / 6
• Subtask 6: 16 / 16
• Subtask 7: 28 / 28