제출 #134128

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

match

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;
typedef long long llong;
typedef pair<int, int> pii;

char S[100002];
int n;
int C[100001];
int P[100001][26];

void solve(int s, int e) {
    if (s > e) return;
    if (S[s] == S[e]) {
        S[s] = '(';
        S[e] = ')';
        solve(s + 1, e - 1);
        return;
    }
    int m = P[e][S[s] - 'a'];
    solve(s, m);
    solve(m + 1, e);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> S + 1;
    n = strlen(S + 1);
    vector<char> st;
    for (int i = 1; i <= n; ++i) {
        if (!st.empty() && st.back() == S[i])
            st.pop_back();
        else st.push_back(S[i]);
    }
    if (!st.empty()) {
        printf("-1\n");
        return 0;
    }
    for (int i = 2; i <= n; ++i) {
        int c = S[i] - 'a';
        if (S[i - 1] == S[i]) C[i] = i - 1;
        else C[i] = P[i - 1][c];
        if (C[i] == 0) continue;
        for (int j = 0; j < 26; ++j) {
            if (j == c) continue;
            if (S[C[i] - 1] == 'a' + j) P[i][j] = C[i] - 1;
            else P[i][j] = P[C[i] - 1][j];
        }
    }
    solve(1, n);
    printf("%s\n", S + 1);
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

match.cpp: In function 'int main()':
match.cpp:30:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     cin >> S + 1;
            ~~^~~

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