Submission #610422

#	Time	Username	Problem	Language	Result	Execution time	Memory
610422		CSQ31	Match (CEOI16_match)	C++17	100 / 100	21 ms	11200 KiB

match

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+1;
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
void bad(){
	cout<<-1;
	exit(0);
}
int dp[26][MAXN];
char ans[MAXN];
string s;
void solve(int l,int r){ //assume [l,r] is solvable
	if(l>r)return;
	if(s[l] == s[r]){ //this is always solvable
		ans[l] = '(';
		ans[r] = ')';
		solve(l+1,r-1);
		return;
	}
	int mid = dp[s[l]-'a'][r];
	ans[l] = '(';
	ans[mid] = ')';
	solve(l+1,mid-1);
	solve(mid+1,r);
}
int main()
{
	cin>>s;
	int n = s.length();
	stack<int>stk;
	for(int i=0;i<n;i++){
		if(stk.empty() || s[stk.top()] != s[i])stk.push(i);
		else stk.pop();
	}
	if(!stk.empty())bad();
	for(int i=0;i<n;i++){
		for(int j=0;j<26;j++)dp[j][i] = -1;
	}
	for(int i=0;i<n;i++){
		dp[s[i]-'a'][i] = i; //empty string
		if(!i)continue;
		int cur = dp[s[i]-'a'][i-1];
		//kek(.....b),a(......)a
		cur--;
		if(cur<0)continue;
		for(int j=0;j<26;j++)dp[j][i] = max(dp[j][i],dp[j][cur]);
	}
	solve(0,n-1);
	for(int i=0;i<n;i++)cout<<ans[i];
}

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