제출 #500380

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
500380		SirCovidThe19th	Match (CEOI16_match)	C++17	0 / 100	6 ms	10444 KiB

match

#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, pt] [pt + 1, r]

    ans[l] = '('; ans[pt] = ')';
    ans[pt + 1] = '('; ans[r] = ')';

    solve(l + 1, pt - 1); solve(pt + 2, r - 1);
}

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];
        }
    }
    solve(0, n - 1);
    FOR(i, 0, n) cout<<ans[i];
}

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