Submission #1256482

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256482		cattuong	괄호 문자열 (CEOI16_match)	C++20	100 / 100	18 ms	21312 KiB

match

#include <bits/stdc++.h>
#define CatTuong ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
using namespace std;
const int N=1e5+5;
string s;
char f[N+5];
vector<array<int,26>>dp;
void build(int l,int r){
    stack<pair<int,int>>st;
    st.push({l,r});
    while(!st.empty()){
        auto seg=st.top();
        st.pop();
        int L=seg.first,R=seg.second;
        if(L>R)
            continue;
        f[L]='(';
        int closePos=dp[R][s[L]-'a'];
        f[closePos]=')';
        st.push({closePos+1,R});
        st.push({L+1,closePos-1});
    }
}
signed main(){
    #define Tuong "cattuong"
//    freopen(Tuong".inp","r",stdin);
//    freopen(Tuong".out","w",stdout);
    CatTuong
    cin>>s;
    int n=s.size();
    s=" "+s;
    stack<int> st;
    for(int i=1;i<=n;i++){
        if(!st.empty() && st.top()==s[i]-'a')
            st.pop();
        else st.push(s[i]-'a');
    }
    if(!st.empty()){
        cout<<-1;
        return 0;
    }
    dp.assign(n+1,{});
    for(int i=1;i<=n;i++){
        dp[i]=dp[i-1];
        dp[i][s[i]-'a']=i;
        int prev=dp[i-1][s[i]-'a'];
        if(prev>0){
            for(int c=0;c<26;c++)
                if(c!=s[i]-'a')
                    dp[i][c]=dp[prev-1][c];
        }
    }
    build(1,n);
    for(int i=1;i<=n;i++)
        cout<<f[i];
    return 0;
}

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