Submission #1221793

#TimeUsernameProblemLanguageResultExecution timeMemory
1221793LucaIlie괄호 문자열 (CEOI16_match)C++20
0 / 100
0 ms320 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(), l);
    if (ptr == pos[(int)s[l]].end())
        return true;
    
    int p = *ptr;
    if (p > r)
        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...