oj.uz

Submission #548263

# Submission time Handle Problem Language Result Execution time Memory
548263 2022-04-12T20:25:08 Z leaked Match (CEOI16_match) C++17
37 / 100
 2000 ms 2112 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 2 ms 1192 KB Output is correct
3 Correct 1 ms 1120 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 2 ms 1192 KB Output is correct
3 Correct 1 ms 1120 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 1136 KB Output is correct
7 Correct 14 ms 1108 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 2 ms 1192 KB Output is correct
3 Correct 1 ms 1120 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 1136 KB Output is correct
7 Correct 14 ms 1108 KB Output is correct
8 Correct 147 ms 1188 KB Output is correct
9 Correct 174 ms 1212 KB Output is correct
10 Correct 170 ms 1108 KB Output is correct
11 Correct 163 ms 1232 KB Output is correct
12 Execution timed out 2071 ms 2112 KB Time limit exceeded
13 Halted 0 ms 0 KB -