제출 #103668

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
103668		Anai	괄호 문자열 (CEOI16_match)	C++14	100 / 100	18 ms	11776 KiB

match

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

const int N = 1e5 + 5, S = 26;


char str[N], ant[N];
int dp[S][N];

int n;

static void solve(int l, int r) {
	if (l > r)
		return;
	int match = dp[str[l] - 'a'][r];

	if (!match)
		throw -1;

	ant[l] = '(';
	ant[match] = ')';

	solve(l + 1, match - 1);
	solve(match + 1, r); }

int main() {
#ifdef HOME
	freopen("match.in", "r", stdin);
	freopen("match.out", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	vector<int> stk;
	stk.reserve(N);

	cin >> (str + 1);
	n = strlen(str + 1);

	for (int i = 1; i <= n; ++i) {
		dp[str[i] - 'a'][i] = i;
		if (i == 1)
			continue;

		int pos = dp[str[i] - 'a'][i - 1];
		if (pos <= 1)
			continue;

		for (int ch = 0; ch < S; ++ch) {
			if (str[i] != ch + 'a')
				dp[ch][i] = dp[ch][pos - 1]; } }

	try {
		solve(1, n); }
	catch (int e) {
		cout << "-1\n";
		return 0; }

	cout << (ant + 1) << endl;

	return 0; }

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