Submission #467369

#	Time	Username	Problem	Language	Result	Execution time	Memory
467369		fuad27	Match (CEOI16_match)	C++17	100 / 100	19 ms	12332 KiB

match

#include <bits/stdc++.h>
using namespace std;
char s[100010],ans[100010];
int op[100010][26];
void solve(int l, int r) {
	if(l > r) return;
	if(op[r][s[l]-'a'] <= l) { cout<<-1<<endl;; exit(0); }
	ans[l] = '(', ans[op[r][s[l]-'a']] = ')';
	solve(l+1, op[r][s[l]-'a']-1), solve(op[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') op[i][j] = i;
			else if(i && op[i-1][s[i]-'a'] > 0) op[i][j] = op[op[i-1][s[i]-'a']-1][j];
			else op[i][j] = -1;
	}
	solve(0,n-1);
	cout<<ans;
	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]
   12 |  scanf("%s", s);
      |  ~~~~~^~~~~~~~~

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