Submission #467369

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
467369	2021-08-22T18:22:29 Z	fuad27	Match (CEOI16_match)	C++17	100 / 100	19 ms	12332 KB

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

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.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	304 KB	Output is correct

Subtask #2

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	304 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	460 KB	Output is correct
7	Correct	1 ms	460 KB	Output is correct

Subtask #3

63.0 / 63.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	304 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	460 KB	Output is correct
7	Correct	1 ms	460 KB	Output is correct
8	Correct	1 ms	972 KB	Output is correct
9	Correct	1 ms	1100 KB	Output is correct
10	Correct	1 ms	1100 KB	Output is correct
11	Correct	1 ms	1228 KB	Output is correct
12	Correct	10 ms	7600 KB	Output is correct
13	Correct	8 ms	8268 KB	Output is correct
14	Correct	9 ms	9020 KB	Output is correct
15	Correct	10 ms	10700 KB	Output is correct
16	Correct	11 ms	10792 KB	Output is correct
17	Correct	12 ms	11212 KB	Output is correct
18	Correct	12 ms	10572 KB	Output is correct
19	Correct	13 ms	11496 KB	Output is correct
20	Correct	13 ms	7756 KB	Output is correct
21	Correct	19 ms	12332 KB	Output is correct