Submission #930250

#	Time	Username	Problem	Language	Result	Execution time	Memory
930250		ttamx	Match (CEOI16_match)	C++14	10 / 100	1 ms	348 KiB

match

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+5;

int n;
int tot[30],cnt[30];
string t,ans;
stack<int> s;

void compress(int i){
    ans[i]=')';
    while(!s.empty()&&t[s.top()]!=t[i]){
        int id=s.top();
        s.pop();
        cnt[t[id]-'a']--;
        compress(id);
    }
    if(s.empty())cout << -1,exit(0);
    int c=t[s.top()]-'a';
    cnt[c]--;
    tot[c]-=2;
    s.pop();
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> t;
    n=t.size();
    for(auto x:t)tot[x-'a']++;
    for(int i=0;i<26;i++)if(tot[i]&1)cout << -1,exit(0);
    for(int i=0;i<n;i++){
        int c=t[i]-'a';
        ans.push_back('(');
        if(cnt[c]>=tot[c]/2){
            compress(i);
        }else{
            cnt[c]++;
            s.emplace(i);
        }
    }
    cout << ans;
}

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