oj.uz

Submission #545905

# Submission time Handle Problem Language Result Execution time Memory
545905 2022-04-05T16:06:14 Z rainboy Match (CEOI16_match) C
100 / 100
 12 ms 10944 KB 
#include <stdio.h>
#include <string.h>
 
#define N	100000
#define A	26
 
int main() {
	static char cc[N + 1], cc_[N + 1], ans[N + 1];
	static int ii[N][A], qu[N];
	int n, i, j, a, cnt;
 
	scanf("%s", cc), n = strlen(cc);
	cnt = 0;
	for (i = 0; i < n; i++)
		if (cnt == 0 || cc_[cnt - 1] != cc[i])
			cc_[cnt++] = cc[i];
		else
			cnt--;
	if (cnt != 0) {
		printf("-1\n");
		return 0;
	}
	for (j = 0; j < n; j++) {
		i = j == 0 ? -1 : ii[j - 1][cc[j] - 'a'] - 1;
		for (a = 0; a < A; a++)
			ii[j][a] = cc[j] == a + 'a' ? j : (i < 0 ? -1 : ii[i][a]);
	}
	cnt = 0;
	for (i = 0; i < n; i++) {
		a = cc[i] - 'a';
		if (cnt == 0 || cc_[cnt - 1] != cc[i] || qu[cnt - 1] > i && ii[qu[cnt - 1] - 1][a] > i)
			cc_[cnt] = cc[i], qu[cnt] = ii[(cnt == 0 ? n : qu[cnt - 1]) - 1][a], cnt++, ans[i] = '(';
		else
			cnt--, ans[i] = ')';
	}
	printf("%s\n", cnt == 0 ? ans : "-1");
	return 0;
}

Compilation message

match.c: In function 'main':
match.c:31:60: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   31 |   if (cnt == 0 || cc_[cnt - 1] != cc[i] || qu[cnt - 1] > i && ii[qu[cnt - 1] - 1][a] > i)
      |                                            ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
match.c:12:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |  scanf("%s", cc), n = strlen(cc);
      |  ^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 296 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 296 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 288 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 1 ms 420 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 296 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 288 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 1 ms 420 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 1 ms 932 KB Output is correct
11 Correct 1 ms 1064 KB Output is correct
12 Correct 6 ms 6700 KB Output is correct
13 Correct 7 ms 7252 KB Output is correct
14 Correct 7 ms 7764 KB Output is correct
15 Correct 8 ms 8824 KB Output is correct
16 Correct 9 ms 8912 KB Output is correct
17 Correct 9 ms 9428 KB Output is correct
18 Correct 10 ms 9864 KB Output is correct
19 Correct 9 ms 10324 KB Output is correct
20 Correct 5 ms 6740 KB Output is correct
21 Correct 12 ms 10944 KB Output is correct