Submission #476185

#	Time	Username	Problem	Language	Result	Execution time	Memory
476185		MohamedAhmed04	Match (CEOI16_match)	C++14	0 / 100	2081 ms	332 KiB

match

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 1e5 + 10 ;

int arr[MAX] ;
int n ;

string s ;
stack<char>st ;

int prv[MAX][26] ;

char ans[MAX] ;

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

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>s ;
	n = s.size() ;
	s = '#' + s ;
	for(int i = 1 ; i <= n ; ++i)
	{
		if(st.size() && st.top() == s[i])
			st.pop() ;
		else
			st.push(s[i]) ; 
	}
	if(st.size())
		return cout<<-1<<"\n" , 0 ;
	for(int i = 1 ; i <= n ; ++i)
	{
		int x = prv[i-1][(s[i] - 'a')] ;
		for(int j = 0 ; j < 2 ; ++j)
		{
			if((s[i] - 'a') == j)
				prv[i][j] = i ;
			else if(x)
				prv[i][j] = prv[x-1][j] ;
		}
	}
	solve(1 , n) ;
	for(int i = 1 ; i <= n ; ++i)
		cout<<ans[i] ;
	cout<<"\n" ;
	return 0 ;
}		

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