oj.uz

Submission #930250

# Submission time Handle Problem Language Result Execution time Memory
930250 2024-02-19T07:52:00 Z ttamx Match (CEOI16_match) C++14
10 / 100
 1 ms 348 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -