제출 #566537

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
566537		Redhood	괄호 문자열 (CEOI16_match)	C++14	100 / 100	16 ms	12372 KiB

match

#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;
}

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