| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 616111 | elpro123 | Match (CEOI16_match) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 1e+7;
long long N;
string s;
char ans[MAXN];
bool check(stack<char> st, long long x){
//mira si entra en el caso de ser una cadena vacia
for(long long i = x; i<N; i++){
//cout<<s[i]<<" "<<st.top()<<"\n";
if(!st.empty() && s[i] == st.top()){//hay un par de iguales ()
st.pop();
}else{//no hay un par, hay otro elemento distinto
st.push(s[i]);
}
//cout<<st.empty()<<"\n";
}
return st.empty();
}
long long main() {
cin>>s;
N=s.length();
stack<char> st;
for(long long i = 0; i < N; i++) {
st.push(s[i]);
if(check(st, i + 1)){//se habre con (
ans[i] = '(';
}else{//hay otro distinto
ans[i] = ')';
st.pop();
//si nos quedamos sin elementos y no se completaron los pares, -1
//o no se puede formar un par con los elementos sobrantes, -1
if(st.empty() || st.top() != s[i]){
cout<<"-1\n";
return 0;
}
st.pop();//procedemos a verificar otro par
}
//cout<<st.top()<<"\n";
}
if(st.empty()){
for(long long i = 0; i < N; i++){
cout << ans[i];
}
}else{
cout<<"-1\n";
}
return 0;
}