Submission #52821

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
52821	2018-06-27T01:28:45 Z	ainta(#1378)	Match (CEOI16_match)	C++11	100 / 100	45 ms	20744 KB

match

#include<cstdio>
#include<algorithm>
#define N_ 101000
using namespace std;
char p[N_], r[N_];
int n, D[N_][27], w[N_], Bef[N_][20];
int cur[N_], st[N_], top;
bool OK(int b, int e) {
	if (b > e)return false;
	for (int i = 19; i >= 0; i--) {
		if (Bef[e][i] >= b)e = Bef[e][i];
	}
	return b == e;
}
int main() {
	//freopen("input.txt", "r", stdin);
	int i, j;
	scanf("%s", p + 1);
	for (i = 1; p[i]; i++);
	n = i - 1;
	for (i = 1; i <= n; i++) {
		w[i] = p[i] - 'a' + 1;
	}

	for (i = 0; i <= n; i++) {
		Bef[i][0] = -1;
		for (j = 0; j <= 26; j++)D[i][j] = -1;
		D[i][w[i]] = 0;
		if (!i)continue;
		if (D[i - 1][w[i]] != -1) {
			int L = D[i - 1][w[i]] + 2;
			Bef[i][0] = i - L;
			if(w[i-L]!=w[i])D[i][w[i - L]] = L;
			for (j = 0; j <= 26; j++) {
				if (D[i - L][j] != -1) {
					if (D[i][j] == -1 || D[i][j] > D[i - L][j] + L)D[i][j] = D[i - L][j] + L;
				}
			}
		}
	}
	for (i = 0; i < 19; i++) {
		for (j = 1; j <= n; j++) {
			if (Bef[j][i] == -1)Bef[j][i + 1] = -1;
			else Bef[j][i + 1] = Bef[Bef[j][i]][i];
		}
	}

	for (i = 1; i <= n; i++) {
		if (top && st[top] == w[i])top--;
		else st[++top] = w[i];
	}
	if (top) {
		puts("-1");
		return 0;
	}
	cur[0] = n;
	for (i = 1; i <= n; i++) {
		r[i] = '(';
		st[++top] = w[i];
		int t = D[cur[top-1]][w[i]];
		if (t == -1) {
			top -= 2;
			r[i] = ')';
			continue;
		}
		cur[top] = cur[top - 1] - t - 1;
		if (!OK(i, cur[top])) {
			top -= 2;
			r[i] = ')';
			continue;
		}
	}
	printf("%s\n", r + 1);
}

Compilation message

match.cpp: In function 'int main()':
match.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", p + 1);
  ~~~~~^~~~~~~~~~~~~

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	488 KB	Output is correct
3	Correct	2 ms	504 KB	Output is correct

Subtask #2

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	488 KB	Output is correct
3	Correct	2 ms	504 KB	Output is correct
4	Correct	2 ms	700 KB	Output is correct
5	Correct	2 ms	752 KB	Output is correct
6	Correct	2 ms	848 KB	Output is correct
7	Correct	3 ms	1020 KB	Output is correct

Subtask #3

63.0 / 63.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	488 KB	Output is correct
3	Correct	2 ms	504 KB	Output is correct
4	Correct	2 ms	700 KB	Output is correct
5	Correct	2 ms	752 KB	Output is correct
6	Correct	2 ms	848 KB	Output is correct
7	Correct	3 ms	1020 KB	Output is correct
8	Correct	4 ms	1788 KB	Output is correct
9	Correct	5 ms	1916 KB	Output is correct
10	Correct	5 ms	1932 KB	Output is correct
11	Correct	4 ms	1948 KB	Output is correct
12	Correct	21 ms	12204 KB	Output is correct
13	Correct	26 ms	13372 KB	Output is correct
14	Correct	27 ms	14368 KB	Output is correct
15	Correct	31 ms	16356 KB	Output is correct
16	Correct	33 ms	16564 KB	Output is correct
17	Correct	36 ms	17588 KB	Output is correct
18	Correct	42 ms	18452 KB	Output is correct
19	Correct	45 ms	19536 KB	Output is correct
20	Correct	23 ms	19536 KB	Output is correct
21	Correct	39 ms	20744 KB	Output is correct