제출 #1293904

#제출 시각아이디문제언어결과실행 시간메모리
1293904xosqedemrufo괄호 문자열 (CEOI16_match)C++20
0 / 100
0 ms332 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;
bool dp[MAXN][MAXN];
int ch[MAXN][MAXN];
signed main(){
    fastio;
    #ifndef ONLINE_JUDGE
    //freopen("100points.txt(i hope)","r",stdin);
    //freopen("100points.out(i hope)","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;
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                dp[i][j] = false;
                ch[i][j] = -1;
            }
        }
        for(int len=2;len<=n;len++){
            for(int i=0;i+len-1<n;i++){
                int j = i + len - 1;
                for(int k=i+1;k<=j;k++){
                    if(s[i]==s[k]){
                        bool left;
                        if(i+1>k-1){
                            left = true;
                        }
                        else{
                            left = dp[i+1][k-1];
                        }
                        if(!left){
                            continue;
                        }
                        bool right;
                        if(k+1>j){
                            right = true;
                        }
                        else{
                            right = dp[k+1][j];
                        }
                        if(!right){
                            continue;
                        }
                        dp[i][j] = true;
                        ch[i][j] = k;
                        break;
                    }
                }
            }
        }
        if(!dp[0][n-1]){
            cout << -1 << endl;
            continue;
        }
        string b(n,'?');
        vector<pii> st;
        st.pb({0,n-1});
        while(!st.empty()){
            pii cur = st.back();
            st.pop_back();
            int i = cur.ff;
            int j = cur.ss;
            if(i>j){
                continue;
            }
            if(i==j){
                continue;
            }
            int k = ch[i][j];
            if(k==-1){
                continue;
            }
            b[i] = '(';
            b[k] = ')';
            if(i+1<=k-1){
                st.pb({i+1,k-1});
            }
            if(k+1<=j){
                st.pb({k+1,j});
            }
        }
        int bal = 0;
        bool ok = true;
        for(int i=0;i<n;i++){
            if(b[i]=='('){
                bal++;
            }
            else if(b[i]==')'){
                bal--;
            }
            else{
                ok = false;
                break;
            }
            if(bal<0){
                ok = false;
                break;
            }
        }
        if(!ok or bal!=0){
            cout << -1 << endl;
            continue;
        }
        cout << b << endl;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...