Submission #1118069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118069		vjudge1	Match (CEOI16_match)	C++17	100 / 100	26 ms	22776 KiB

match

//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define ll long long
#define endl "\n"
#define AI ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
ll dp[100001][26];
string a;
string res;
void solve(ll l,ll r)
{
    //cout<<l<<' '<<r;
    if(l<r)
    {
        ll x=dp[r][a[l]-'a'];
        //cout<<l<<' '<<r<<' '<<x<<endl;
        res[l-1]='(';
        res[x-1]=')';
        res[r-1]=')';
        if(l+1<x-1)
        solve(l+1,x-1);
        if(x+1<r)
        solve(x+1,r);
    }
    return;
}
int main()
{
    //AI
    //freopen(“kangaroo.in”, “r”, stdin);
    // freopen(“kangaroo.out”, “w”, stdout);
    ll i,j,k,n;
    cin>>a;
    res=a;
    //cout<<res;
    n=a.size();
    stack<char>s;
    for(i=0;i<n;i++)
    {
        if(s.size() and s.top()==a[i])
        s.pop();
        else
        s.push(a[i]);
    }
    if(s.size())
    {
        cout<<-1<<endl;
        return 0;
    }
    a="#"+a;//dp[i][j]=dp[dp[i-1][a[i]]-1][c[i]]
    //cout<<res;
    for(i=1;i<=n;i++)
    {
        for(j=0;j<26;j++)
        {
            dp[i][j]=0;
            if(a[i]==char('a'+j))
            dp[i][j]=i;
            else if(dp[i-1][char(a[i]-'a')]>0)
            {
              //  cout<<i<<' '<<j;
                dp[i][j]=dp[dp[i-1][a[i]-'a']-1][j];
            }
          //  cout<<dp[i][j]<<' ';
        }
        //cout<<endl;
    }

    solve(1,n);
    cout<<res;
}

Compilation message (stderr)

match.cpp: In function 'int main()':
match.cpp:59:29: warning: array subscript has type 'char' [-Wchar-subscripts]
   59 |             else if(dp[i-1][char(a[i]-'a')]>0)
      |                             ^~~~~~~~~~~~~~
match.cpp:32:12: warning: unused variable 'k' [-Wunused-variable]
   32 |     ll i,j,k,n;
      |            ^

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