Submission #616112

#	Time	Username	Problem	Language	Result	Execution time	Memory
616112		elpro123	Match (CEOI16_match)	C++14	37 / 100	2072 ms	716 KiB

match

#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();
}
 
int main() {//xd
	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;

}

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