제출 #476186

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
476186		MohamedAhmed04	괄호 문자열 (CEOI16_match)	C++14	100 / 100	17 ms	12516 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 < 26 ; ++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: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 63 / 63