oj.uz

Submission #548285

# Submission time Handle Problem Language Result Execution time Memory
548285 2022-04-12T21:18:49 Z leaked Match (CEOI16_match) C++17
100 / 100
 14 ms 10804 KB 
#include <bits/stdc++.h>

#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
#define fast_prep ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
//#define int long long
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
const int N=1e5+1;
int last[N][26];
string ans;
signed main(){
    fast_prep;
    string s;
    cin>>s;
    int n=sz(s);
    ans.resize(n);
    stack<pii> st;
    st.push({-1,-1});
    for(int i=0;i<n;i++){
        for(int j=0;j<26;j++) last[i][j]=-1;
        last[i][s[i]-'a']=i;
        for(int j=0;j<26;j++){
            if(i){
                if(last[i-1][s[i]-'a']>0){
//                    cout<<"WOT "<<
                    umax(last[i][j],last[last[i-1][s[i]-'a']-1][j]);
                }
            }
//            cout<<"I "<<i<<' '<<last[i][j]<<endl;
        }
    }
//    for(int i=n-1;i>=0;i--)
    queue<pii>q;
    q.push({0,n-1});
    while(!q.empty()){
        auto [l,r]=q.front();
//        cout<<"WAT "<<l<<' '<<r<<endl;
        q.pop();
//        if(s[l]==s[r]){
//            ans[l]='(';ans[r]=')';
//            if(l+1<=r-1)
//                q.push({l+1,r-1});
//            continue;
//        }
        int j=last[r][s[l]-'a'];
//        c
//        if(s[i]==)
        if(j<=l){
            cout<<-1;
            return 0;
        }
        ans[l]='(';ans[j]=')';
        pii wt={l+1,j-1};
        pii o={j+1,r};
        if(o.f<=o.s) q.push(o);
        if(wt.f<=wt.s) q.push(wt);
    }
    cout<<ans;
    return 0;
}
/*
abbaaa
cbbbbccbbccbbbbbbc
(((((((()))())))))

*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 452 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 452 KB Output is correct
8 Correct 2 ms 980 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 2 ms 980 KB Output is correct
11 Correct 2 ms 976 KB Output is correct
12 Correct 8 ms 6612 KB Output is correct
13 Correct 8 ms 7188 KB Output is correct
14 Correct 9 ms 7708 KB Output is correct
15 Correct 10 ms 8792 KB Output is correct
16 Correct 10 ms 8788 KB Output is correct
17 Correct 10 ms 9304 KB Output is correct
18 Correct 11 ms 9812 KB Output is correct
19 Correct 12 ms 10308 KB Output is correct
20 Correct 7 ms 6616 KB Output is correct
21 Correct 14 ms 10804 KB Output is correct