Submission #250565

#TimeUsernameProblemLanguageResultExecution timeMemory
250565Osama_AlkhodairyMatch (CEOI16_match)C++17
37 / 100
2065 ms1000 KiB
#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

int n;
string s;

void apply(vector <char> &g, char c){
    if(g.size() > 0 && g.back() == c) g.pop_back();
    else g.push_back(c);
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> s;
    n = s.size();
    s = ';' + s;
    vector <char> cur;
    string ans(n + 1, ';');
    vector <int> r(n + 1, n);
    for(int i = 1 ; i <= n ; i++){
        if(ans[i] != ';') continue;
        vector <char> c = cur;
        int t = -1;
        for(int j = i ; j <= r[i] ; j++){
            apply(c, s[j]);
            if(c == cur && s[j] == s[i]) t = j;
        }
        if(t == -1) finish(-1);
        ans[i] = '(';
        ans[t] = ')';
        for(int j = i ; j <= t ; j++){
            r[j] = t;
        }
        apply(cur, s[i]);
    }
    cout << ans.substr(1) << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...