제출 #1221800

#제출 시각아이디문제언어결과실행 시간메모리
1221800LucaIlie괄호 문자열 (CEOI16_match)C++20
10 / 100
0 ms328 KiB
#include <bits/stdc++.h>

using namespace std;

string s, sol;
vector<int> pos[26];

bool solve(int l, int r) {
    if (l > r)
        return true;

    auto ptr = upper_bound(pos[(int)s[l]].begin(), pos[(int)s[l]].end(), r);
    if (ptr == pos[(int)s[l]].begin())
        return false;
    ptr--;
    
    int p = *ptr;
    if (p > r || p <= l)
        return false;


    // printf("%d %d\n", l, r);
    sol[l] = '(';
    sol[p] = ')';

    return (solve(l + 1, p - 1) & solve(p + 1, r));
}

int main() {
    int n;

    cin >> s;
    n = s.size();
    sol.resize(n);

    for (int i = 0; i < n; i++) {
        s[i] -= 'a';
        pos[(int)s[i]].push_back(i);
    }

    bool isSol = solve(0, n - 1);

    if (isSol) 
        cout << sol << "\n";
    else
        cout << "-1\n";

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...