oj.uz

Submission #52819

# Submission time Handle Problem Language Result Execution time Memory
52819 2018-06-27T01:22:04 Z ainta(#1378) Match (CEOI16_match) C++11
0 / 100
 2 ms 560 KB 
#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], st[N_];
bool OK(int b, int e) {
	for (int i = 19; i >= 0; i--) {
		if (Bef[e][i] >= b)e = Bef[e][i];
	}
	return b == e;
}
bool Pos(int pv) {
	int i, top = 0;
	for (i = 1; i <= pv; i++) {
		if (r[i] == '(')st[++top] = w[i];
		else {
			if (top && st[top] == w[i])top--;
			else return false;
		}
	}
	int cur = n;
	for (i = 1; i <= top; i++) {
		if (D[cur][st[i]] == -1)return false;
		cur = cur - D[cur][st[i]] - 1;
		if (cur < pv)return false;
	}
	return OK(pv, cur);
}
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 (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];
		}
	}

	if (!Pos(0)) {
		puts("-1");
		return 0;
	}
	for (i = 1; i <= n; i++) {
		r[i] = '(';
		if (!Pos(i)) {
			r[i] = ')';
		}
	}
	printf("%s\n", r + 1);
}

Compilation message

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Incorrect 2 ms 560 KB Output isn't correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Incorrect 2 ms 560 KB Output isn't correct

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Incorrect 2 ms 560 KB Output isn't correct