제출 #1242831

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

match

// coached by rainboy
#include <algorithm>
#include <iostream>
#include <cstring>

using namespace std;

const int N = 100000;
const int A = 26;

char aa[N + 1], bb[N + 1];
int pp[N], qq[N][A], ll[N], rr[N];

int main() {
	cin >> aa;
	int n = strlen(aa);
	for (int i = 0; i < n; i++)
		aa[i] -= 'a';
	for (int i = 0; i < n; i++) {
		int a = aa[i], p = pp[i] = i ? qq[i - 1][a] : -1;
		for (int a = 0; a < A; a++)
			qq[i][a] = p > 0 ? qq[p - 1][a] : -1;
		qq[i][a] = i;
	}
	for (int cnt = 0, l = 0, r = n - 1; l < n; l++) {
		int a = aa[l];
		if (qq[r][a] > l) {
			ll[cnt] = l, rr[cnt] = r, cnt++;
			bb[l] = '(', r = qq[r][a] - 1;
			continue;
		}
		if (!cnt || a != aa[ll[cnt - 1]]) {
			cout << "-1\n";
			return 0;
		}
		bb[l] = ')', r = rr[--cnt];
	}
	bb[n] = '\0';
	cout << bb << '\n';
	return 0;
}

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