Submission #445736

#	Time	Username	Problem	Language	Result	Execution time	Memory
445736		Nima_Naderi	괄호 문자열 (CEOI16_match)	C++14	100 / 100	22 ms	21220 KiB

match

///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

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 63 / 63