Submission #845416

#	Time	Username	Problem	Language	Result	Execution time	Memory
845416		1bin	Match (CEOI16_match)	C++14	100 / 100	9 ms	12712 KiB

match

#include<bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 1e5 + 5;
int n, a[NMAX], dp[NMAX][26], ans[NMAX];
string s;

int go(int l, int r){
	if(l > r) return 1;
	int x = dp[r][a[l]];
	if(x <= l) return 0;

	ans[l] = 1; ans[r] = -1;
	return go(l + 1, x - 1) && go(x + 1, r);
}

int main(void){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> s;
	n = s.size();
	for(int i = 1; i <= n; i++) a[i] = s[i - 1] - 'a';
	memset(dp, -1, sizeof(dp));
	for(int i = 1; i <= n; i++)
		for(int j = 0; j < 26; j++){
			if(a[i] == j) dp[i][j] = i;
			else if(dp[i - 1][a[i]] >= 1) dp[i][j] = dp[dp[i - 1][a[i]] - 1][j];
		}
	if(!go(1, n)) cout << -1;
	else{
		for(int i = 1; i <= n; i++) cout << (ans[i] == 1 ? '(' : ')');
	}
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 63 / 63