제출 #134370

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

match

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

const int MAXN = 100005;

char s[MAXN];
int par[MAXN], chi[MAXN][26], non;
vector<int> idx[MAXN][26];
int no[MAXN];
char ans[MAXN];

bool solve(int l, int r) {
	if(l > r) return true;
	vector<int> &v = idx[no[l - 1]][s[l] - 'a'];
	int k = upper_bound(v.begin(), v.end(), r) - v.begin();
	if(k == 0 || v[k - 1] <= l) return false;
	ans[l] = '(';
	ans[v[k - 1]] = ')';
	return solve(l + 1, v[k - 1] - 1) && solve(v[k - 1] + 1, r);
}

int main() {
	int N;

	cin >> (s + 1);

	for(N = 1; s[N]; N++);
	N--;

	stack<int> st;
	par[0] = -1;
	for(int i = 0; i < 26; i++) chi[0][i] = -1;
	no[0] = 0;
	non = 1;
	for(int i = 1; i <= N; i++) {
		if(!st.empty() && st.top() == s[i]) {
			no[i] = par[no[i - 1]];
			idx[no[i]][s[i] - 'a'].push_back(i);
			st.pop();
		}
		else {
			if(chi[no[i - 1]][s[i] - 'a'] == -1) {
				par[non] = no[i - 1];
				for(int j = 0; j < 26; j++) chi[non][j] = -1;
				chi[no[i - 1]][s[i] - 'a'] = non++;
			}
			no[i] = chi[no[i -1]][s[i] - 'a'];
			idx[no[i]][s[i] - 'a'].push_back(i);
			st.push(s[i]);
		}
	}

	if(solve(1, N)) for(int i = 1; i <= N; i++) cout << ans[i];
	else cout << -1;
	return 0;
}

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