Submission #129981

#	Time	Username	Problem	Language	Result	Execution time	Memory
129981		TadijaSebez	Match (CEOI16_match)	C++11	100 / 100	20 ms	11640 KiB

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 (stderr)

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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 63 / 63