제출 #1143748

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1143748		mnbvcxz123	괄호 문자열 (CEOI16_match)	C++20	100 / 100	40 ms	28224 KiB

match

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

constexpr int N=1e5+5;

string s;
ll n,dp[N][26];
string f(ll l, ll r){
    if(l>r)return "";
    return '('+f(l+1,dp[r][s[l]-'a']-1)+')'+f(dp[r][s[l]-'a']+1,r);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>s;
    n=s.size();
    s='0'+s;
    stack<ll>S;
    for(int i=1;i<=n;++i){
        if(!S.empty() and S.top()==s[i])S.pop();
        else S.push(s[i]);
    }
    if(!S.empty()){
        cout<<-1<<'\n';
        return 0;
    }
    for (ll i = 2; i <= n; i++)
    for (ll j = 0; j < 26; j++) if (j + 'a' == s[i]) dp[i][j] = i;
    else dp[i][j] = dp[i - 1][s[i] - 'a'] - 1 < 0 ? 0 : dp[dp[i - 1][s[i] - 'a'] - 1][j];
    cout<<f(1,n)<<'\n';
}

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