oj.uz

답안 #616112

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
616112 2022-07-31T21:57:37 Z elpro123 괄호 문자열 (CEOI16_match) C++14
37 / 100
 2000 ms 716 KB 
#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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 4 ms 212 KB Output is correct
7 Correct 7 ms 316 KB Output is correct

Subtask #3
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 4 ms 212 KB Output is correct
7 Correct 7 ms 316 KB Output is correct
8 Correct 93 ms 304 KB Output is correct
9 Correct 100 ms 340 KB Output is correct
10 Correct 92 ms 312 KB Output is correct
11 Correct 76 ms 324 KB Output is correct
12 Execution timed out 2072 ms 716 KB Time limit exceeded
13 Halted 0 ms 0 KB -