제출 #155078

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

match

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

const int MAXN = 1e5+5;

string S;
int N;
int prevStart[MAXN][26];
stack<int> stk;

string solve(int a, int b) {
    if (a > b) return "";
    if (a+1 == b) return "()";
    int idx = prevStart[b][S[a]-'a'];
    return '(' + solve(a+1,idx-1) + ')' + solve(idx+1,b);
}

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> S;
    N = S.length();
    memset(prevStart, -1, sizeof prevStart);

    FOR(i,0,N-1){
        FOR(j,0,25){
            if (j == S[i]-'a') prevStart[i][j] = i;
            else {
                if (i == 0 or prevStart[i-1][S[i]-'a'] <= 0) prevStart[i][j] = -1;
                else prevStart[i][j] = prevStart[prevStart[i-1][S[i]-'a']-1][j];
            }
        }
    }

    FOR(i,0,N-1){
        if (!stk.empty() and S[stk.top()] == S[i]) stk.pop();
        else stk.push(i);
    }

    if (!stk.empty()) cout << -1 << '\n';
    else cout << solve(0,N-1) << '\n';
}

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