답안 #129981

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
129981	2019-07-13T17:17:06 Z	TadijaSebez	괄호 문자열 (CEOI16_match)	C++11	100 / 100	20 ms	11640 KB

match

#include <bits/stdc++.h>
using namespace std;
const int N=100050;
char s[N],ans[N];
int pre[N][26];
bool ok=1;
void Solve(int l, int r)
{
	if(l>r) return;
	int m=pre[r][s[l]-'a'];
	if(m<=l){ ok=0;return;}
	ans[l]='(';
	ans[m]=')';
	Solve(l+1,m-1);
	Solve(m+1,r);
}
int main()
{
	int n;
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;i++) for(int j=0;j<26;j++)
	{
        if(j==s[i]-'a') pre[i][j]=i;
        else if(pre[i-1][s[i]-'a']>0) pre[i][j]=pre[pre[i-1][s[i]-'a']-1][j];
        else pre[i][j]=0;
	}
	Solve(1,n);
	if(ok) printf("%s",ans+1);
	else printf("-1\n");
	return 0;
}

Compilation message

match.cpp: In function 'int main()':
match.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",s+1);
  ~~~~~^~~~~~~~~~

Subtask #1

10.0 / 10.0

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

Subtask #2

27.0 / 27.0

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

Subtask #3

63.0 / 63.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	504 KB	Output is correct
7	Correct	3 ms	504 KB	Output is correct
8	Correct	3 ms	1016 KB	Output is correct
9	Correct	4 ms	1144 KB	Output is correct
10	Correct	3 ms	1144 KB	Output is correct
11	Correct	3 ms	1144 KB	Output is correct
12	Correct	12 ms	7160 KB	Output is correct
13	Correct	13 ms	7800 KB	Output is correct
14	Correct	15 ms	8412 KB	Output is correct
15	Correct	15 ms	9848 KB	Output is correct
16	Correct	15 ms	9776 KB	Output is correct
17	Correct	16 ms	10360 KB	Output is correct
18	Correct	17 ms	10232 KB	Output is correct
19	Correct	18 ms	11000 KB	Output is correct
20	Correct	12 ms	7288 KB	Output is correct
21	Correct	20 ms	11640 KB	Output is correct