oj.uz

답안 #845416

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
845416 2023-09-06T13:31:49 Z 1bin 괄호 문자열 (CEOI16_match) C++14
100 / 100
 9 ms 12712 KB 
#include<bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 1e5 + 5;
int n, a[NMAX], dp[NMAX][26], ans[NMAX];
string s;

int go(int l, int r){
	if(l > r) return 1;
	int x = dp[r][a[l]];
	if(x <= l) return 0;

	ans[l] = 1; ans[r] = -1;
	return go(l + 1, x - 1) && go(x + 1, r);
}

int main(void){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> s;
	n = s.size();
	for(int i = 1; i <= n; i++) a[i] = s[i - 1] - 'a';
	memset(dp, -1, sizeof(dp));
	for(int i = 1; i <= n; i++)
		for(int j = 0; j < 26; j++){
			if(a[i] == j) dp[i][j] = i;
			else if(dp[i - 1][a[i]] >= 1) dp[i][j] = dp[dp[i - 1][a[i]] - 1][j];
		}
	if(!go(1, n)) cout << -1;
	else{
		for(int i = 1; i <= n; i++) cout << (ans[i] == 1 ? '(' : ')');
	}
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

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

Subtask #3
63.0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10840 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 3 ms 10844 KB Output is correct
9 Correct 3 ms 10840 KB Output is correct
10 Correct 2 ms 10840 KB Output is correct
11 Correct 2 ms 10968 KB Output is correct
12 Correct 5 ms 11868 KB Output is correct
13 Correct 6 ms 11868 KB Output is correct
14 Correct 6 ms 12340 KB Output is correct
15 Correct 7 ms 12636 KB Output is correct
16 Correct 9 ms 12512 KB Output is correct
17 Correct 7 ms 12636 KB Output is correct
18 Correct 7 ms 12136 KB Output is correct
19 Correct 8 ms 12480 KB Output is correct
20 Correct 6 ms 12124 KB Output is correct
21 Correct 9 ms 12712 KB Output is correct