Submission #1293937

#TimeUsernameProblemLanguageResultExecution timeMemory
1293937xosqedemrufoMatch (CEOI16_match)C++20
100 / 100
1357 ms12100 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;
int n;
string s,ans;
bool dfs(int l,int r){
    if(l==r){
        return 0;
    }
    if(l>r){
        return 1;
    }
    if(s[l]==s[r]){
        ans[l]='(';
        ans[r]=')';
        return dfs(l+1,r-1);
    }
    stack<char> st;
    for(int i=r;i>l;i--){
        if(st.empty() or st.top()!=s[i]){
            st.push(s[i]);
        } 
        else{
            st.pop();
            if(st.empty() and s[i-1]==s[l]){
                ans[l]='(';
                ans[i-1]=')';
                return dfs(l+1,i-2) and dfs(i,r);
            }
        }
    }
    return 0;
}
signed main(){
    fastio;
    #ifndef ONLINE_JUDGE
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    #endif
    int t=1;
    //cin >> t;
    while(t--){
        cin >> s;
        n = s.size();
        s = "#"+s;
        ans = string(n+1,'?');
        bool ok = dfs(1,n);
        if(ok){
            for(int i=1;i<=n;i++){
                cout << ans[i];
            }
            cout << endl;
        }
        else{
            cout << -1 << endl;
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...