제출 #1236786

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1236786		franuch	괄호 문자열 (CEOI16_match)	C++20	10 / 100	9 ms	324 KiB

match

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vc vector
#define st first
#define nd second
#define all(a) a.begin(), a.end()
#define sz(a) (ll)a.size()
#define pub push_back
#define pob pop_back

void program() {
	string str;
	cin >> str;
	ll n = sz(str);
	string ans = "-1";
	for (ll mask = 0; mask < (1 << n); mask++) {
		if (__builtin_popcountll(mask) != n / 2)
			continue;
		string a(n, '0');
		for (ll i = 0; i < n; i++)
			a[i] = (mask & (1 << i)) != 0 ? '(' : ')';

		stack<ll> s;
		ll git = true;
		for (ll i = 0; i < n; i++) {
			if (a[i] == '(')
				s.push(i);
			else {
				if (s.empty() or str[s.top()] != str[i]) {
					git = false;
					break;
				}
				s.pop();
			}
		}
		if (git)
			ans = min(ans, a);
	}
	cout << ans << "\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	program();
	return 0;
}

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