oj.uz

Submission #475687

# Submission time Handle Problem Language Result Execution time Memory
475687 2021-09-23T16:24:46 Z Blobo2_Blobo2 Match (CEOI16_match) C++14
0 / 100
 1 ms 204 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,tune=native")
#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 cnt;
void solve(int l=0,int r = s.size()-1){
    if(!cnt){
        cout<<ans;
        exit(0);
    }
    //cout<<l<<' '<<r<<' '<<ans<<' ';
    if(l>r)
        return;
    if(s[l] == s[r] && r%2!=l%2 && ans[l]!='(' && ans[l]!=')'){
        //cout<<"ok1"<<endl;
        bool ok=0;
        for(int i=0;i<26;i++){
            if(v[i].empty())continue;
            int szl = upper_bound(all(v[i]),l) - v[i].begin();
            int s=0,e=v[i].size()-1;
            while(s<=e){
                int mid=(s+e)>>1;
                if(v[i][mid]>=r)e=mid-1;
                else s=mid+1;
            }
            int szr = e;
            if((szr-szl+1)%2 == 1){
                ok=1;
                goto a;
            }
        }
        ans[l]='(';
        ans[r]=')';
        cnt-=2;
        solve(l+1,r-1);
        solve(r+1,s.size()-1);
    }
    else{
        //cout<<"ok2"<<endl;
        a:;
        solve(l,r-1);
    }
}
signed main(){
    Blobo2_el_7akim_elly_3ayz_yro7_IOI_w_3ayz_yakol_jilaty
    cin>>s;
    int n=s.size();
    cnt=n;
    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;
    }
    solve();
    cout<<ans<<endl;
    return 0;
}

Compilation message

match.cpp: In function 'void solve(long long int, long long int)':
match.cpp:36:14: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   36 |         bool ok=0;
      |              ^~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -