제출 #548285

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
548285		leaked	괄호 문자열 (CEOI16_match)	C++17	100 / 100	14 ms	10804 KiB

match

#include <bits/stdc++.h>

#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
#define fast_prep ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
//#define int long long
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
const int N=1e5+1;
int last[N][26];
string ans;
signed main(){
    fast_prep;
    string s;
    cin>>s;
    int n=sz(s);
    ans.resize(n);
    stack<pii> st;
    st.push({-1,-1});
    for(int i=0;i<n;i++){
        for(int j=0;j<26;j++) last[i][j]=-1;
        last[i][s[i]-'a']=i;
        for(int j=0;j<26;j++){
            if(i){
                if(last[i-1][s[i]-'a']>0){
//                    cout<<"WOT "<<
                    umax(last[i][j],last[last[i-1][s[i]-'a']-1][j]);
                }
            }
//            cout<<"I "<<i<<' '<<last[i][j]<<endl;
        }
    }
//    for(int i=n-1;i>=0;i--)
    queue<pii>q;
    q.push({0,n-1});
    while(!q.empty()){
        auto [l,r]=q.front();
//        cout<<"WAT "<<l<<' '<<r<<endl;
        q.pop();
//        if(s[l]==s[r]){
//            ans[l]='(';ans[r]=')';
//            if(l+1<=r-1)
//                q.push({l+1,r-1});
//            continue;
//        }
        int j=last[r][s[l]-'a'];
//        c
//        if(s[i]==)
        if(j<=l){
            cout<<-1;
            return 0;
        }
        ans[l]='(';ans[j]=')';
        pii wt={l+1,j-1};
        pii o={j+1,r};
        if(o.f<=o.s) q.push(o);
        if(wt.f<=wt.s) q.push(wt);
    }
    cout<<ans;
    return 0;
}
/*
abbaaa
cbbbbccbbccbbbbbbc
(((((((()))())))))

*/

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