oj.uz

Submission #1118069

# Submission time Handle Problem Language Result Execution time Memory
1118069 2024-11-24T21:18:35 Z vjudge1 Match (CEOI16_match) C++17
100 / 100
 26 ms 22776 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)
{
    //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

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.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 336 KB Output is correct

Subtask #2
27.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 336 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 848 KB Output is correct

Subtask #3
63.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 336 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 848 KB Output is correct
8 Correct 2 ms 1616 KB Output is correct
9 Correct 2 ms 1872 KB Output is correct
10 Correct 2 ms 1872 KB Output is correct
11 Correct 2 ms 1872 KB Output is correct
12 Correct 16 ms 13860 KB Output is correct
13 Correct 14 ms 15056 KB Output is correct
14 Correct 21 ms 16464 KB Output is correct
15 Correct 17 ms 19024 KB Output is correct
16 Correct 17 ms 19008 KB Output is correct
17 Correct 21 ms 20064 KB Output is correct
18 Correct 19 ms 19792 KB Output is correct
19 Correct 23 ms 21444 KB Output is correct
20 Correct 16 ms 14160 KB Output is correct
21 Correct 26 ms 22776 KB Output is correct