Submission #545905

#	Time	Username	Problem	Language	Result	Execution time	Memory
545905		rainboy	Match (CEOI16_match)	C11	100 / 100	12 ms	10944 KiB

match

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

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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 63 / 63