Submission #339682

#	Time	Username	Problem	Language	Result	Execution time	Memory
339682		couplefire	괄호 문자열 (CEOI16_match)	C++17	0 / 100	1 ms	376 KiB

match

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005

int n; string s;
int dp[MAXN];
string ans;

bool solve(int l, int r){
    if(l == r+1) return 1;
    if(dp[l] == -1) return false;
    ans[l] = '('; ans[dp[l]] = ')';
    return solve(l+1, dp[l]-1) && solve(dp[l]+1, r);
}

int main(){
    // freopen("match.in", "r", stdin);
    // freopen("match.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> s; n = s.length();
    ans.resize(n);
    dp[n] = -1;
    for(int i = n-1; i>=0; i--){
        dp[i] = -1;
        if(i != n-1 && s[i] == s[i+1]) dp[i] = i+1;
        int cur = i+1;
        while(dp[cur] != -1){
            cur = dp[cur]+1;
            if(cur != n && s[cur] == s[i]) dp[i] = cur;
        }
    }
    if(!solve(0, n-1)) cout << -1 << endl;
    else cout << ans << endl;
}

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