Submission #53125

#	Time	Username	Problem	Language	Result	Execution time	Memory
53125		youngyojun	Match (CEOI16_match)	C++11	100 / 100	22 ms	12604 KiB

match

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

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