Submission #445632

#	Time	Username	Problem	Language	Result	Execution time	Memory
445632		soroush	Match (CEOI16_match)	C++17	10 / 100	2076 ms	16132 KiB

match

#pragma GCC target("popcnt")
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int , int> pii;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int maxn = 2010;
const ll mod = 1e9+7;
 
#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}
 
int n;
string s;
char ans[maxn];
int dp[maxn][maxn];
 
bool chk(int l , int r){
	if(~dp[l][r])return dp[l][r];
	if(l >= r)return (dp[l][r] = 1);
	for(int i = l + 1 ; i < r ; i ++)if(s[i] == s[l])
		if(chk(l+1, i) && chk(i+1 , r))return (dp[l][r] = 1);
	return (dp[l][r] = 0);
}
 
void solve(int l , int r){
	if(l >= r)return;
	for(int i = r - 1 ; i > l ; i --)if(s[i] == s[l])
		if(chk(l+1, i) && chk(i+1 , r)){
			ans[l] = '(' , ans[i] = ')';
			solve(l + 1 , i) , solve(i + 1 , r);
			return;
		}
}
 
int32_t main(){
	cin.tie(0)->sync_with_stdio(0);
	ms(dp , -1);
	cin >> s;
	n = s.size();
	if(chk(0 , n)){
		solve(0, n);
		for(int i = 0 ; i < n ; i ++)
			cout << ans[i];
	}
	else
		cout << -1;
	return(0);
}

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