제출 #609167

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
609167		AkramElOmrani	괄호 문자열 (CEOI16_match)	C++17	100 / 100	1498 ms	3620 KiB

match

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ios ios_base::sync_with_stdio(0);cin.tie(0);

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
 
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int gen(int a, int b) {return (ll)rng() % (b - a + 1) + a;}

const int alp = 26;

int main()
{
	ios

	string s; cin >> s;
	int n = s.length();
	vector<int> st(n + 1);
	string ans(n, '?');
	function<bool(int, int)> can = [&](int l, int r) {
		int last = 0;
		if(l > r) return true;
		if((r - l + 1) & 1) return false;
		if(s[l] == s[r]) {
			ans[l] = '(', ans[r] = ')';
			return can(l + 1, r - 1);
		}
		for(int i = r; l <= i; --i) {
			if(!last || st[last - 1] != s[i]) st[last++] = s[i];
			else {
				--last;
				if(last <= 0 && l < i - 1 && s[l] == s[i - 1]) {
					ans[l] = '(', ans[i - 1] = ')';
					return can(l + 1, i - 2) && can(i, r);
				}
			}
		}
		return false;
	};
	if(can(0, n - 1)) {
		cout << ans;
	} else {
		cout << -1;
	}
	cout << '\n';
}

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