Submission #61215

#	Time	Username	Problem	Language	Result	Execution time	Memory
61215		junodeveloper	Match (CEOI16_match)	C++17	100 / 100	25 ms	12852 KiB

match

#include <bits/stdc++.h>
using namespace std;
char s[100010],a[100010];
int pre[100010][26];
void solve(int l, int r) {
	if(l > r) return;
	if(pre[r][s[l]-'a'] <= l) { puts("-1"); exit(0); }
	a[l] = '(', a[pre[r][s[l]-'a']] = ')';
	solve(l+1, pre[r][s[l]-'a']-1), solve(pre[r][s[l]-'a']+1, r);
}
int main() {
	scanf("%s", s);
	int n = strlen(s);
	for(int i=0; i<n; i++) {
		for(int j=0; j<26; j++)
			if(j == s[i]-'a') pre[i][j] = i;
			else if(i && pre[i-1][s[i]-'a'] > 0) pre[i][j] = pre[pre[i-1][s[i]-'a']-1][j];
			else pre[i][j] = -1;
	}
	solve(0,n-1);
	puts(a);
	return 0;
}

Compilation message (stderr)

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

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