oj.uz

Submission #476130

# Submission time Handle Problem Language Result Execution time Memory
476130 2021-09-24T23:13:16 Z Blobo2_Blobo2 Match (CEOI16_match) C++14
100 / 100
 15 ms 12048 KB 
/*
Editor: Abdelrahman Hossam
Nickname: Blobo2_Blobo2
IOI next year isA :)
*/
/*#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-funroll-all-loops,-fpeel-loops,-funswitch-loops")*/

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define endl "\n"
#define all(v)  v.begin(),v.end()
#define gen(arr,n,nxt)  generate(arr,arr+n,nxt)
#define Blobo2_el_7akim_elly_3ayz_yro7_IOI_w_3ayz_yakol_jilaty ios_base::sync_with_stdio(false);cin.tie(0);
#define EPS 0.00000001

const int mo=1e9+7,INF=1e18;
int nxt(){int x;cin>>x;return x;}
string s,ans;
vector<int>v[26];
int prv[100001][26];
inline void solve(int l=0,int r = s.size()-1){
    if(l>r)
        return;
    int idxl = l;
    int idxr = prv[r][s[l]-'a'];
    ans[idxl] = '(';
    ans[idxr] = ')';
    solve(idxl+1,idxr-1);
    solve(idxr+1,r);
}
signed main(){
    Blobo2_el_7akim_elly_3ayz_yro7_IOI_w_3ayz_yakol_jilaty
    cin>>s;
    int n=s.size();
    for(int i=0;i<n;i++)
        v[s[i]-'a'].push_back(i),ans+='*';
    stack<int>st;
    for(int i=0;i<n;i++){
        if(!st.empty() && st.top() == s[i])st.pop();
        else st.push(s[i]);
    }
    if(st.size()){
        cout<<-1<<endl;
        return 0;
    }
    memset(prv,-1,sizeof prv);
    for(int i=0;i<n;i++){
        prv[i][s[i]-'a'] = i;
        if(!i)continue;
        for(int j=0;j<26;j++){
            if(j == s[i]-'a')continue;
            if(prv[i-1][s[i]-'a']>0)
                prv[i][j] = prv[prv[i-1][s[i]-'a']-1][j];
        }
    }
    /*for(int i=0;i<n;i++){
        cout<<prv[i][0]<<' '<<prv[i][1]<<endl;
    }*/
    solve();
    cout<<ans<<endl;
    return 0;
}

Compilation message

match.cpp:21:24: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   21 | const int mo=1e9+7,INF=1e18;
      |                        ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10444 KB Output is correct
2 Correct 4 ms 10444 KB Output is correct
3 Correct 0 ms 204 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10444 KB Output is correct
2 Correct 4 ms 10444 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 4 ms 10444 KB Output is correct
5 Correct 4 ms 10444 KB Output is correct
6 Correct 4 ms 10432 KB Output is correct
7 Correct 4 ms 10412 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10444 KB Output is correct
2 Correct 4 ms 10444 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 4 ms 10444 KB Output is correct
5 Correct 4 ms 10444 KB Output is correct
6 Correct 4 ms 10432 KB Output is correct
7 Correct 4 ms 10412 KB Output is correct
8 Correct 5 ms 10444 KB Output is correct
9 Correct 5 ms 10572 KB Output is correct
10 Correct 6 ms 10564 KB Output is correct
11 Correct 6 ms 10572 KB Output is correct
12 Correct 13 ms 11388 KB Output is correct
13 Correct 11 ms 11596 KB Output is correct
14 Correct 12 ms 11660 KB Output is correct
15 Correct 14 ms 11992 KB Output is correct
16 Correct 13 ms 12048 KB Output is correct
17 Correct 13 ms 11928 KB Output is correct
18 Correct 14 ms 11668 KB Output is correct
19 Correct 14 ms 11888 KB Output is correct
20 Correct 10 ms 11596 KB Output is correct
21 Correct 15 ms 11972 KB Output is correct