제출 #566537

#제출 시각아이디문제언어결과실행 시간메모리
566537Redhood괄호 문자열 (CEOI16_match)C++14
100 / 100
16 ms12372 KiB
#include <bits/stdc++.h>

using namespace std;
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()

typedef long long ll;
typedef long double ld;

const int N = (int)1e5 + 10;
string s;
int bst[N][26];
int n;
string answer;
bool bad = 0;
void solve(int l , int r){
    if(l > r)
        return;
    answer[l] = '(';
    int x;
    if(s[l] == s[r])
        x = r;
    else
        x = bst[r][s[l]-'a'];
    if(x == -1 || x < l){
        bad = 1;
        return;
    }
    answer[x] = ')';
    solve(l + 1 , x - 1);
    solve(x + 1 , r);
}
int main()
{
    ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
    cin >> s;
    /// unique problem guys
    n = s.size();
    answer = string(n, 'x');
    for(int t=0;t<n;++t){
        for(int tt=0;tt<26;++tt)
            bst[t][tt]=-1;
    }
    for(int i = 1 ; i < n; ++i){
        for(int j = 0; j < 26; ++j){
            int x;
            if(s[i - 1] == s[i]){
                x = i-1;
            }else{
                x = bst[i - 1][s[i]-'a'];
            }
            if(x == -1)
                continue;
            assert(s[x] == s[i]);
            if(x - 1 >= 0 && s[x - 1]-'a' == j){
                bst[i][j] = x - 1;
            }else if(x - 1 >= 0){
                bst[i][j] = bst[x - 1][j];
            }
        }
    }
    /// abbaaa
//    cerr << " damn \n";
//    cout << bst[2][0] << endl;



    solve(0 , n - 1);


//    cout << "lol " << answer << endl;

    if(bad)
        cout << -1 << '\n';
    else
        cout << answer << '\n';
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...