제출 #536308

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
536308		jerzyk	괄호 문자열 (CEOI16_match)	C++17	100 / 100	15 ms	12620 KiB

match

#include<bits/stdc++.h>

using namespace std;
const int N = 100 * 1000 + 7;
int dp[26][N];
string s, w;
stack<char> st;

void Ans(int l, int r)
{
    if(l >= r) 
        return;
    int k = dp[s[l] - 'a'][r];
    //cout << l << " " << r << " " << k << " " << w << "\n";
    w[l] = '('; w[k] = ')';
    Ans(l + 1, k - 1); Ans(k + 1, r);
}

void Solve()
{
    int n, x;
    cin >> s; n = s.size();
    for(int i = 1; i <= n; ++i)
        w.push_back('.');
    for(int i = 0; i < n; ++i)
    {
        if(st.size() > 0 && st.top() == s[i])
            st.pop();
        else
            st.push(s[i]);
    }
    if(st.size())
    {
        cout << -1 << "\n"; return;
    }
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < 26; ++j)
        {
            if(j == s[i] - 'a')
                dp[j][i] = i;
            else if(i != 0)
            {
                x = dp[s[i] - 'a'][i - 1];
                if(x != 0)
                    dp[j][i] = dp[j][x - 1];
            }
        }
    }
    Ans(0, n - 1);
    cout << w << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    Solve();

    return 0;
}

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