제출 #1293968

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1293968		ulvix	괄호 문자열 (CEOI16_match)	C++20	0 / 100	1 ms	568 KiB

match

#include <bits/stdc++.h>
#ifdef ULVI
    #define db(x)          cerr<<"[ "<<#x<<" = "<<(x)<<" ]\n"
    #define dbv(v)         cerr<<#v<<" = [ ";for(auto &__x : v)cerr<<__x<<' ';cerr<<"]\n"
    #define line()         cerr<<string(80, '-')<<'\n'
#else
    #define db(x)
    #define dbv(v)
    #define line()
#endif
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define ff first
#define ss second
#define enld endl
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll sz=2e5+100;
const ll mod=1e9+7;
const ll inf=1e18;
template<class T>
using indexed_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

void solve(){
    string s;
    cin>>s;
    ll n=s.size();
    vector<vector<ll>> v(n+5,vector<ll>(30));
    for(ll i=n-2;i>=0;i--){
        v[i]=v[i+1];
        v[i][s[i+1]-'a']++;
    }
    vector<pair<char,ll>> st;
    vector<ll> cnt(30);
    string ans(n,'&');
    for(ll i=0;i<n;i++){
        bool u=0;
        if(!st.empty()){
            auto [a,b]=st.back();
            ll rem=v[i][a-'a'];
            if(rem<cnt[a-'a']){
                if(s[i]!=a || rem<cnt[a-'a']-1){
                    cout<<"-1\n";
                    return;
                }
                u=1;
            }
        }
        if(!u){
            ans[i]='(';
            if(st.empty()||st.back().ff!=s[i]) st.push_back({s[i],1});
            else st.back().ss++;
            cnt[s[i]-'a']++;

        }
        else{
            ans[i]=')';
            st.back().ss--;
            cnt[st.back().ff-'a']--;
            if(!st.back().ss) st.pop_back();
        }
    }
    if(!st.empty()){
        cout<<"-1\n";
        return;
    }
    cout<<ans<<'\n';
}

int main(){
    //freopen("match.in","r",stdin);
    //freopen("match.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t=1;
    //cin>>t;
    for(ll _=1;_<=t;_++){
        //cout<<"Scenario #"<<_<<":\n";
        solve();
    }
}

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