oj.uz

답안 #313171

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
313171 2020-10-15T11:55:06 Z two_sides 괄호 문자열 (CEOI16_match) C++17
100 / 100
 8 ms 2804 KB 
#include <bits/stdc++.h>
using namespace std;

string s; int n;
vector <int> p;

void rec(int l, int r) {
	if (l > r) return;
	if (s[l] == s[r]) {
		cout << '(';
		rec(l + 1, r - 1);
		cout << ')';
		return;
	}
	int m = p[r];
	while (s[m - 1] != s[l])
		m =	p[m - 1];
	cout << '(';
	rec(l + 1, m - 2);
	cout << ')';
	rec(m, r);
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> s; n = s.size();
	for (int i = 0; i < n; i++) {
		if (!p.empty() && s[p.back()] == s[i])
			p.pop_back();
		else p.push_back(i);
	}
	if (p.size()) {
		cout << "-1\n"; return 0;
	}
	p.assign(n, -1);
	for (int i = 1; i < n; i++) {
		p[i] = i - 1;
		while (p[i] >= 0 && s[p[i]] != s[i])
			p[i] = p[p[i]] - 1;
	}
	rec(0, n - 1);
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct

Subtask #3
63.0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 4 ms 1664 KB Output is correct
13 Correct 4 ms 1792 KB Output is correct
14 Correct 5 ms 2288 KB Output is correct
15 Correct 8 ms 2560 KB Output is correct
16 Correct 6 ms 2560 KB Output is correct
17 Correct 6 ms 2688 KB Output is correct
18 Correct 6 ms 1664 KB Output is correct
19 Correct 7 ms 2304 KB Output is correct
20 Correct 5 ms 1976 KB Output is correct
21 Correct 7 ms 2804 KB Output is correct