제출 #1117958

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1117958		vjudge1	괄호 문자열 (CEOI16_match)	C++17	10 / 100	2029 ms	2424 KiB

match

#include <bits/stdc++.h>
#define GOOD_LUCK ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define itn int
#define INF 100000000
#define MOD 998244353
#define MAX 103
#define endl "\n"
#define ff first
#define ss second
using namespace std;

int temp;
string a;
int n;

string solve(int x, stack <char> s, string st) {
	if (x == n-1) {
		if (s.empty()) {
			return st;
		}
		else {
			return "-1";
		}
	}
	x++;
	if (s.empty()) {
		s.push(a[x]);
		string ans = solve(x, s, st + '(');
//				cout << ans;
		return ans;
	}
	else if (s.top() == a[x]) {
		string ans1, ans2;
		// 1.
		s.pop();
		ans1 = solve(x, s, st + ')');
		// 2.
		s.push(a[x]);
		s.push(a[x]);
		ans2 = solve(x, s, st + '(');
//				cout << ans1 << ' ' << ans2 << endl;
		if (ans1 == "-1") return ans2;
		else if (ans2 == "-1") return ans1;
		else return min(ans1, ans2);
	}
	else {
		s.push(a[x]);
		string ans = solve(x, s, st + '(');
		return ans;
	}
}

signed main() {

	GOOD_LUCK

    int t;
	t = 1;
//	cin >> t;
    while (t--) {
        cin >> a;
        n = a.size();
        if (n % 2 != 0) {
        	cout << -1;
        	continue;
		}
		string st = "";
		stack <char> s;
		cout << solve(-1, s, st);
	}

    return 0;
}
// Problem B
// by Ekber_Ekber

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