Submission #1293889

#TimeUsernameProblemLanguageResultExecution timeMemory
1293889xosqedemrufoMatch (CEOI16_match)C++20
10 / 100
2095 ms572 KiB
//Author RufatM
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<string> vs;
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
#define pb push_back
#define pf push_front
#define eb emplace_back
#define ff first
#define ss second
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)
#define mt19937_64 mt_rand(chrono::steady_clock::now().time_since_epoch().count())
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
const int MOD=1000000007;
const int INF=1000000007;
const ll LINF=4e18;
const int MAXN=2005;
signed main(){
    fastio;
    #ifndef ONLINE_JUDGE
    //freopen("input.txt","r",stdin);
    //freopen("output.x","w",stdout);
    #endif
    int t=1;
    //cin >> t;
    while(t--){
        string s;
        cin >> s;
        int n = s.size();
        if(n%2==1){
            cout << -1 << endl;
            continue;
        }
        bool found = false;
        string best;
        for(int mask=0;mask<(1<<n);mask++){
            string b(n,'(');
            for(int i=0;i<n;i++){
                if(mask & (1<<i)){
                    b[i] = ')';
                }
            }
            int bal = 0;
            bool ok = true;
            for(int i=0;i<n;i++){
                if(b[i]=='('){
                    bal++;
                }
                else{
                    bal--;
                }
                if(bal<0){
                    ok = false;
                    break;
                }
            }
            if(!ok){
                continue;
            }
            if(bal!=0){
                continue;
            }
            vi st;
            ok = true;
            for(int i=0;i<n;i++){
                if(b[i]=='('){
                    st.pb(i);
                }
                else{
                    if(st.empty()){
                        ok = false;
                        break;
                    }
                    int j = st.back();
                    st.pop_back();
                    if(s[j]!=s[i]){
                        ok = false;
                        break;
                    }
                }
            }
            if(!ok){
                continue;
            }
            if(!st.empty()){
                continue;
            }
            if(!found or b<best){
                best = b;
                found = true;
            }
        }
        if(!found){
            cout << -1 << endl;
        }
        else{
            cout << best << endl;
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...