oj.uz

Submission #1118071

# Submission time Handle Problem Language Result Execution time Memory
1118071 2024-11-24T21:29:03 Z vjudge1 Match (CEOI16_match) C++17
10 / 100
 2000 ms 2640 KB 
//#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)///aaabba
{
    if(l==r)
    res[l-1]='(';
    if(l<r)
    {
        ll x=dp[r][a[l]-'a'];
      //  cout<<l<<' '<<r<<' '<<x<<endl;
        res[l-1]='(';
        res[x-1]=')';
        res[r-1]=')';
        solve(l+1,x-1);
        solve(x+1,r-1);
    }
    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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 504 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Execution timed out 2061 ms 2640 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Execution timed out 2061 ms 2640 KB Time limit exceeded
5 Halted 0 ms 0 KB -