제출 #467625

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

match

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    string s;
    cin >> s;
    int n=s.size();
    s="$"+s;
    vector<array<int,26>> trie(1);
    trie[0].fill(-1);
    vector<int> p(1,-1);
    int id=0;
    int now=0;
    auto mv=[&](char c)
    {
        if(trie[now][c-'a']==-1)
        {
            trie[now][c-'a']=++id;
            trie.emplace_back();
            trie.back().fill(-1);
            p.push_back(now);
        }
        now=trie[now][c-'a'];
    };
    string t;
    vector<array<int,26>> mx(n+1);
    for(int i=0;i<=n;i++) mx[i].fill(-1);
    vector<array<int,26>> opt(n+1);
    for(int i=1;i<=n;i++)
    {
        if(t.empty()||t.back()!=s[i])
        {
            mv(s[i]);
            t+=s[i];
        }
        else
        {
            now=p[now];
            t.pop_back();
        }
        mx[now][s[i]-'a']=i;
        for(int j=0;j<26;j++) opt[i][j]=mx[now][j];
    }
    if(t.empty())
    {
        string res(n+1,'$');
        function<void(int,int)> go=[&](int l,int r)
        {
            if(l==r+1) return;
            res[l]='(';
            int m=opt[r][s[l]-'a'];
            res[m]=')';
            go(l+1,m-1);
            go(m+1,r);
        };
        go(1,n);
        cout << res.substr(1,n) << "\n";
    }
    else cout << "-1\n";
    return 0;
}

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