Submission #940145

#	Time	Username	Problem	Language	Result	Execution time	Memory
940145		12345678	Match (CEOI16_match)	C++17	100 / 100	8 ms	15304 KiB

match

#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5;

int n, dp[nx][30], vl[nx], ans[nx];
string s;
stack<int> st;

void solve(int l, int r)
{
    if (r<l) return;
    ans[dp[r][vl[l]]]=1;
    //cout<<l<<' '<<r<<' '<<dp[r][vl[l]]<<'\n';
    solve(l+1, dp[r][vl[l]]-1);
    solve(dp[r][vl[l]]+1, r);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>s;
    n=s.size();
    for (int i=0; i<n; i++) vl[i+1]=s[i]-'a';
    for (auto x:s)
    {
        if (st.empty()||st.top()!=x) st.push(x);
        else st.pop();
    }
    if (!st.empty()) return cout<<-1, 0;
    for (int i=1; i<=n; i++)
    {
        int p=dp[i-1][vl[i]]-1;
        if (p>=0) for (int j=0; j<26; j++) dp[i][j]=dp[p][j];
        dp[i][vl[i]]=i;
    }
    solve(1, n);
    for (int i=1; i<=n; i++) cout<<(ans[i]?')':'(');
}

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