제출 #37352

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
37352		cheater2k	괄호 문자열 (CEOI16_match)	C++14	37 / 100	13 ms	16880 KiB

match

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

const int N = 1e5 + 5;

string s;
int n, prv[N];
int jump[N][18], mask[N][18];
char res[N];

void out() { cout << "-1\n"; exit(0); }

void solve(int l, int r) {
	if (l > r) return;
	if (s[l] == s[r]) {
		res[l] = '('; res[r] = ')'; // valid
		return solve(l + 1, r - 1);
	}

	int ch = s[l] - 'a';
	int cur = r;
	if (mask[cur][17] & (1 << ch)) {
		for (int i = 16; i >= 0; --i) if (!(mask[cur][i] & (1 << ch))) {
			cur = jump[cur][i];
		}
	} else out(); // invalid

	if (cur == -1) out();
	cur = jump[cur][0];
	if (cur <= l || s[cur] != s[l]) out(); 

	// s[cur] is the matching bracket of s[l]
	res[l] = '('; res[cur] = ')';
	solve(l + 1, cur - 1);
	solve(cur + 1, r);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> s, n = s.size();

	prv[0] = -1;
	for (int i = 1; i < n; ++i) {
		if (s[i] == s[i - 1]) { prv[i] = i - 1; continue; }
		int cur = i - 1;
		while(cur >= 0 && s[cur] != s[i]) {
			cur = prv[cur] - 1;
		}
		prv[i] = max(cur, -1);
	}

	// prepare for RMQ
	for (int i = 0; i < n; ++i) if (prv[i] != -1) {
		jump[i][0] = prv[i] - 1;
		if (prv[i] > 0) mask[i][0] |= (1 << s[prv[i] - 1] - 'a');
	}
	for (int j = 1; j <= 17; ++j) {
		for (int i = 0; i < n; ++i) jump[i][j] = -1;
		for (int i = 0; i < n; ++i) {
			if (jump[i][j - 1] != -1) 
				jump[i][j] = jump[jump[i][j - 1]][j - 1],
				mask[i][j] |= mask[jump[i][j - 1]][j - 1];
			mask[i][j] |= mask[i][j - 1];
		}
	}

	solve(0, n - 1);
	for (int i = 0; i < n; ++i) cout << res[i]; cout << '\n';
}

컴파일 시 표준 에러 (stderr) 메시지

match.cpp: In function 'int main()':
match.cpp:55:53: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   if (prv[i] > 0) mask[i][0] |= (1 << s[prv[i] - 1] - 'a');
                                                     ^

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