제출 #528790

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

match

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

template <class F> struct RecLambda : private F {
    explicit RecLambda(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args> decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::string S;
    std::cin >> S;
    const int N = S.size();
    vector<int> A(N);
    for (int i = 0; i < N; ++i) A[i] = S[i] - 'a';
    vector<array<int, 26>> memo(N + 1);
    vector<array<bool, 26>> done(N + 1);
    const auto rightmost = RecLambda([&](auto&& dfs, const int k, const int c) -> int {
        if (k == 0) return -1;
        if (done[k][c]) return memo[k][c]; 
        done[k][c] = true;
        const int b = A[k - 1];
        if (b == c) return memo[k][c] = k - 1;
        const int m = dfs(k - 1, b);
        if (m == -1) return memo[k][c] = -1;
        return memo[k][c] = dfs(m, c);
    });
    std::string ans;
    if (RecLambda([&](auto&& dfs, const int l, const int r) -> bool {
        if (l == r) return true;
        const int m = rightmost(r, A[l]);
        if (m == -1) return false;
        ans += '(';
        if (!dfs(l + 1, m)) return false;
        ans += ')';
        if (!dfs(m + 1, r)) return false;
        return true;
    })(0, N)) {
        std::cout << ans << '\n';
    } else {
        std::cout << "-1\n";
    }
    return 0;
}

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