Submission #530514

#	Time	Username	Problem	Language	Result	Execution time	Memory
530514		Yazan_Alattar	Match (CEOI16_match)	C++14	100 / 100	29 ms	14020 KiB

match

	#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 100007;
const ll inf = 2e9;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const int dx[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0};

string s;
int n, dp[M][30];
char ans[M];

bool check(int start){
	stack <int> st;
	for(int i = start; i < n; ++i){
		if(st.empty() || s[st.top()] != s[i]) st.push(i);
		else st.pop();
	}
	return st.empty();
}

void solve(int l, int r){
	if(l > r) return;
	int mid = dp[r][s[l] - 'a'];
	
	ans[l] = '(';
	ans[mid] = ')';
	
	solve(l + 1, mid - 1);
	solve(mid + 1, r);
	return;
}

int main()
{
	cin >> s;
	n = s.size();
	
	if(!check(0)) return cout << -1 << endl, 0;
	
	for(int i = 0; i < n; ++i) for(int j = 0; j < 26; ++j) dp[i][j] = -1;
	
	dp[0][s[0] - 'a'] = 0;
	for(int i = 1; i < n; ++i){
		dp[i][s[i] - 'a'] = i;
		for(int j = 0; j < 26; ++j) if(j != s[i] - 'a'){
			int l = dp[i - 1][s[i] - 'a'];
			if(l) dp[i][j] = dp[l - 1][j];
		}
	}
	
	solve(0, n - 1);
	
	for(int i = 0 ; i < n; ++i) cout << ans[i];
	cout << endl;
	return 0;
}

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