제출 #445736

#제출 시각아이디문제언어결과실행 시간메모리
445736Nima_NaderiMatch (CEOI16_match)C++14
100 / 100
22 ms21220 KiB
///In the name of GOD
//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MXN = 3e5 + 10;
const ll SGM = 26;
ll n;
ll mtc[MXN][SGM];
string s, t;
bool Can(ll l, ll r){
    if(l > r) return 1;
    if(l == r) return 0;
    if(s[l] == s[r]){
        t[l] = '(', t[r] = ')';
        return Can(l + 1, r - 1);
    }
    ll m = mtc[r][s[l] - 'a'];
    if(m < l) return 0;
    t[l] = '(', t[m] = ')';
    return Can(l + 1, m - 1) && Can(m + 1, r);
}
int main(){
    //ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    cin >> s, n = s.size();
    s = "$" + s, t = s;
    mtc[1][s[1] - 'a'] = 1;
    for(int i = 2; i <= n; i ++){
        ll c = s[i] - 'a';
        for(int cp = 0; cp < 26; cp ++){
            if(mtc[i - 1][c]){
                mtc[i][cp] = mtc[mtc[i - 1][c] - 1][cp];
            }
        }
        mtc[i][c] = i;
    }
    if(Can(1, n)) cout << t.substr(1, n) << '\n';
    else cout << "-1\n";
    return 0;
}
/*!
    HE'S AN INSTIGATOR,
    ENEMY ELIMINATOR,
    AND WHEN HE KNOCKS YOU BETTER
    YOU BETTER LET HIM IN.
*/
//! N.N
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...