oj.uz

Submission #548265

# Submission time Handle Problem Language Result Execution time Memory
548265 2022-04-12T20:25:23 Z leaked Match (CEOI16_match) C++17
37 / 100
 2000 ms 2236 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;
struct dsu{
    int p[N];
    void make(int v){
        p[v]=v;
    }
    dsu(){
        iota(p,p+N,0);
    }
    int get(int v){
        return p[v]=(p[v]==v?v:get(p[v]));
    }
}lt,rt;

signed main(){
    fast_prep;
    string s;
    cin>>s;
    int n=sz(s);
    vec<int> lft(n),rgt(n);
    string ans(n,'-');
    stack<int> st;
    vec<int>p(n);
    for(int i=0;i<n;i++){
        if(!sz(st)) st.push(i),ans[i]='(';
        else{
            if(s[st.top()]==s[i]){
                ans[i]=')';
                p[st.top()]=i;
                p[i]=st.top();
                st.pop();
            }
            else{
                ans[i]='(';
                st.push(i);
            }
        }
    }
    if(sz(st)){
        cout<<-1;
        return 0;
    }
//    vec<vec<int>> have(26,vec<iCnt>());
//    for(int i=0;i<n;i++) have[s[i]-'a'].pb(i);
    auto check=[&](int j){
        stack<int> stt=st;
        for(int i=j;i<n;i++){
            if(!sz(stt)) stt.push(i),ans[i]='(';
            else{
                if(s[stt.top()]==s[i]){
                    ans[i]=')';
                    stt.pop();
                }
                else{
                    ans[i]='(';
                    stt.push(i);
                }
            }
        }
        return (!sz(stt));
    };
//    cerr<<"ANS "<<ans<<endl;
    for(int i=0;i<n;i++){
//        for(auto &j : {'(',')'}){
            ans[i]='(';
            st.push(i);
            if(check(i+1)){
                continue;
            }
            else{
                st.pop();
                assert(sz(st) && s[st.top()]==s[i]);
                st.pop();
                ans[i]=')';
            }
//        }
    }
    cout<<ans;
    return 0;
}
/*
cbbbbccbbccbbbbbbc
(((((((()))())))))

*/

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 2 ms 1108 KB Output is correct
4 Correct 4 ms 1108 KB Output is correct
5 Correct 4 ms 1108 KB Output is correct
6 Correct 8 ms 1108 KB Output is correct
7 Correct 14 ms 1140 KB Output is correct

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 2 ms 1108 KB Output is correct
4 Correct 4 ms 1108 KB Output is correct
5 Correct 4 ms 1108 KB Output is correct
6 Correct 8 ms 1108 KB Output is correct
7 Correct 14 ms 1140 KB Output is correct
8 Correct 156 ms 1188 KB Output is correct
9 Correct 167 ms 1208 KB Output is correct
10 Correct 179 ms 1204 KB Output is correct
11 Correct 163 ms 1248 KB Output is correct
12 Execution timed out 2084 ms 2236 KB Time limit exceeded
13 Halted 0 ms 0 KB -