Submission #1293920

#TimeUsernameProblemLanguageResultExecution timeMemory
1293920littleprofessorMatch (CEOI16_match)C++20
0 / 100
2 ms568 KiB
/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin>>s;
    int n = s.size();

    vector<char> V(n, '?');
    vector<vector<int>> idx(26);
    for(int i = 0 ; i < n ; i++) {
        idx[s[i] - 'a'].push_back(i);
    }
    
    for(int i = 0 ; i < 26 ; i++) {
        vector<int>& v = idx[i];
        int m = v.size();
        
        if(m % 2 == 1) {
            cout<<-1;
            return 0;
        }
        
        for(int i = 0 ; i < m/2 ; i++) {
            int left = v[i];
            int right = v[m-1-i];

            V[left] = '(';
            V[right] = ')';
        }
    }
    for(char c : V) {
        if (c == '?') {
            cout<<-1;
            return 0;
        }
    }
    vector<int> st;
    for(int i = 0 ; i < n ; i++) {
        if(V[i] == '(') {
            st.push_back(i);
        } 
        else {
            if(st.empty()) {
                cout<<-1;
                return 0;
            }
            int j = st.back(); 
            st.pop_back();
            
            if(s[i] != s[j]) {
                cout<<-1;
                return 0;
            }
        }
    }

    if(!st.empty()) {
        cout<<-1;
        return 0;
    }
    for(char c : V) cout<<c;

    return 0;
}



#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...