oj.uz

Submission #476185

# Submission time Handle Problem Language Result Execution time Memory
476185 2021-09-25T09:19:46 Z MohamedAhmed04 Match (CEOI16_match) C++14
0 / 100
 2000 ms 332 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Execution timed out 2081 ms 332 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Execution timed out 2081 ms 332 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Execution timed out 2081 ms 332 KB Time limit exceeded
3 Halted 0 ms 0 KB -