Submission #500382

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
500382	2021-12-30 19:57:09	SirCovidThe19th	괄호 문자열 (CEOI16_match)	C++17	100 / 100	22 ms	12856 KiB

match

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std; 
#define FOR(i, x, y) for (int i = x; i < y; i++)
int n, dp[100005][26]; string s; char ans[100005];
void solve(int l, int r){
    if (l > r) return;
    int pt = dp[r][s[l] - 'a']; //l matches with pt
    ans[l] = '('; ans[pt] = ')';
    solve(l + 1, pt - 1); solve(pt + 1, r);
}
int main(){
    cin >> s; n = s.size(); 
    
    stack<int> stk;
    FOR(i, 0, n){
        if (stk.empty() or s[stk.top()] != s[i]) stk.push(i);
        else stk.pop();
    }
    if (!stk.empty()){ cout<<-1<<"\n"; return 0; }
    memset(dp, -1, sizeof(dp));
    FOR(i, 0, n) FOR(c, 0, 26){
        if (s[i] - 'a' == c) dp[i][c] = i; 
        else if (i){
            int l = dp[i - 1][s[i] - 'a']; //[l, i] is good
            if (l > 0) dp[i][c] = dp[l - 1][c];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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