oj.uz

Submission #471549

# Submission time Handle Problem Language Result Execution time Memory
471549 2021-09-09T17:43:04 Z rainboy Retro (COCI17_retro) C
30 / 100
 500 ms 6200 KB 
#include <stdio.h>
#include <string.h>

#define N	300
#define M	300

int main() {
	static char s[M + 1]; 
	static int dp[M][N], dq[M][N];
	static long long sp[M][N][5], sq[M][N][5];
	int n, m, i, j, d, d_;

	scanf("%d%d", &n, &m);
	for (j = 0; j < m; j++)
		for (d = 0; d < n; d++)
			dp[j][d] = d == 0 ? 0 : -1;
	for (i = 0; i < n; i++) {
		scanf("%s", s);
		for (j = 0; j < m; j++)
			for (d = 0; d < n; d++) {
				if (s[j] == '*')
					dq[j][d] = d == 0 ? 0 : -1;
				else {
					d_ = s[j] == '.' || s[j] == 'M' ? d : (s[j] == '(' ? d + 1 : d - 1);
					dq[j][d] = -1;
					if (d_ >= 0 && d_ < n) {
						if (dq[j][d] < dp[j][d_] || dq[j][d] == dp[j][d_] && memcmp(sq[j][d], sp[j][d_], sizeof sp[j][d_]) > 0)
							dq[j][d] = dp[j][d_], memcpy(sq[j][d], sp[j][d_], sizeof sp[j][d_]);
						if (j > 0 && (dq[j][d] < dp[j - 1][d_] || dq[j][d] == dp[j - 1][d_] && memcmp(sq[j][d], sp[j - 1][d_], sizeof sp[j - 1][d_]) > 0))
							dq[j][d] = dp[j - 1][d_], memcpy(sq[j][d], sp[j - 1][d_], sizeof sp[j - 1][d_]);
						if (j + 1 < m && (dq[j][d] < dp[j + 1][d_] || dq[j][d] == dp[j + 1][d_] && memcmp(sq[j][d], sp[j + 1][d_], sizeof sp[j + 1][d_]) > 0))
							dq[j][d] = dp[j + 1][d_], memcpy(sq[j][d], sp[j + 1][d_], sizeof sp[j + 1][d_]);
					}
					if (dq[j][d] != -1 && (s[j] == '(' || s[j] == ')')) {
						if (s[j] == ')')
							sq[j][d][4 - dq[j][d] / 60] |= 1LL << 59 - dq[j][d] % 60;
						dq[j][d]++;
					}
				}
			}
		for (j = 0; j < m; j++)
			for (d = 0; d < n; d++) {
				dp[j][d] = dq[j][d];
				if (dq[j][d] != -1)
					memcpy(sp[j][d], sq[j][d], sizeof sq[j][d]);
			}
	}
	for (j = 0; j < m; j++)
		if (s[j] == 'M') {
			int l = dp[j][0];

			printf("%d\n", l);
			while (l--)
				printf("%c", (sp[j][0][4 - l / 60] & 1LL << 59 - l % 60) == 0 ? '(' : ')');
			printf("\n");
			return 0;
		}
	return 0;
}

Compilation message

retro.c: In function 'main':
retro.c:27:57: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   27 |       if (dq[j][d] < dp[j][d_] || dq[j][d] == dp[j][d_] && memcmp(sq[j][d], sp[j][d_], sizeof sp[j][d_]) > 0)
      |                                   ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
retro.c:29:75: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   29 |       if (j > 0 && (dq[j][d] < dp[j - 1][d_] || dq[j][d] == dp[j - 1][d_] && memcmp(sq[j][d], sp[j - 1][d_], sizeof sp[j - 1][d_]) > 0))
      |                                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
retro.c:31:79: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   31 |       if (j + 1 < m && (dq[j][d] < dp[j + 1][d_] || dq[j][d] == dp[j + 1][d_] && memcmp(sq[j][d], sp[j + 1][d_], sizeof sp[j + 1][d_]) > 0))
      |                                                     ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
retro.c:36:49: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   36 |        sq[j][d][4 - dq[j][d] / 60] |= 1LL << 59 - dq[j][d] % 60;
      |                                              ~~~^~~~~~~~~~~~~~~
retro.c:54:52: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   54 |     printf("%c", (sp[j][0][4 - l / 60] & 1LL << 59 - l % 60) == 0 ? '(' : ')');
      |                                                 ~~~^~~~~~~~
retro.c:13:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
retro.c:18:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |   scanf("%s", s);
      |   ^~~~~~~~~~~~~~

Subtask #1
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 332 KB Partially correct
2 Correct 1 ms 460 KB Output is correct
3 Partially correct 1 ms 332 KB Partially correct
4 Partially correct 1 ms 460 KB Partially correct
5 Partially correct 2 ms 1356 KB Partially correct
6 Partially correct 9 ms 1156 KB Partially correct
7 Partially correct 16 ms 1460 KB Partially correct
8 Partially correct 9 ms 712 KB Partially correct
9 Partially correct 20 ms 1192 KB Partially correct
10 Correct 27 ms 1564 KB Output is correct
11 Execution timed out 625 ms 6004 KB Time limit exceeded
12 Execution timed out 551 ms 5600 KB Time limit exceeded
13 Partially correct 274 ms 2504 KB Partially correct
14 Partially correct 246 ms 2396 KB Partially correct
15 Execution timed out 753 ms 6200 KB Time limit exceeded
16 Execution timed out 680 ms 6096 KB Time limit exceeded
17 Execution timed out 570 ms 5112 KB Time limit exceeded
18 Execution timed out 517 ms 4756 KB Time limit exceeded
19 Execution timed out 695 ms 6192 KB Time limit exceeded
20 Execution timed out 632 ms 6000 KB Time limit exceeded