oj.uz

Submission #53125

# Submission time Handle Problem Language Result Execution time Memory
53125 2018-06-28T13:04:40 Z youngyojun Match (CEOI16_match) C++11
100 / 100
 22 ms 12604 KB 
#include <bits/stdc++.h>
#define upmax(a,b) (a)=max((a),(b))
using namespace std;
void fuk() { puts("-1"); exit(0); }

const int MAXN = 100005;

int dp[MAXN][26];

char Ans[MAXN];

int B[MAXN];
char A[MAXN];

int N;

void f(int s, int e) {
	if(s > e) return;
	if((e-s+1)&1) fuk();
	if(s+1 == e) {
		if(B[s] != B[e]) fuk();
		Ans[s] = '(';
		Ans[e] = ')';
		return;
	}
	int k = dp[e][B[s]];
	if(k < s) fuk();
	Ans[s] = '(';
	Ans[k] = ')';
	f(s+1, k-1);
	f(k+1, e);
}

int main() {
	scanf(" %s", A+1);
	N = int(strlen(A+1));
	if(N&1) fuk();

	for(int i = 1; i <= N; i++)
		B[i] = A[i]-'a';
	
	for(int i = 1, j; i <= N; i++) {
		dp[i][B[i]] = i;
		j = dp[i-1][B[i]];
		if(j < 2) continue;
		upmax(dp[i][B[j-1]], j-1);
		for(int c = 0; c < 26; c++)
			upmax(dp[i][c], dp[j-1][c]);
	}

	f(1, N);

	for(int i = 1; i <= N; i++)
		putchar(Ans[i]);
	puts("");
	return 0;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 428 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 2 ms 376 KB Output is correct
3 Correct 2 ms 428 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 3 ms 808 KB Output is correct
7 Correct 2 ms 820 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 2 ms 376 KB Output is correct
3 Correct 2 ms 428 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 3 ms 808 KB Output is correct
7 Correct 2 ms 820 KB Output is correct
8 Correct 3 ms 1260 KB Output is correct
9 Correct 3 ms 1516 KB Output is correct
10 Correct 3 ms 1516 KB Output is correct
11 Correct 4 ms 1548 KB Output is correct
12 Correct 10 ms 7840 KB Output is correct
13 Correct 10 ms 8476 KB Output is correct
14 Correct 11 ms 9244 KB Output is correct
15 Correct 17 ms 10780 KB Output is correct
16 Correct 16 ms 10796 KB Output is correct
17 Correct 16 ms 11324 KB Output is correct
18 Correct 19 ms 11324 KB Output is correct
19 Correct 15 ms 11836 KB Output is correct
20 Correct 13 ms 11836 KB Output is correct
21 Correct 22 ms 12604 KB Output is correct