Submission #1221915

#TimeUsernameProblemLanguageResultExecution timeMemory
1221915LucaIlie괄호 문자열 (CEOI16_match)C++20
10 / 100
639 ms24424 KiB
#include <bits/stdc++.h>

using namespace std;

string s, sol;
vector<int> pos[26];
unordered_map<int, bool> mp[100000];

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

    if (mp[l].find(r) != mp[l].end())
        return mp[l][r];

    auto ptr = upper_bound(pos[(int)s[l]].begin(), pos[(int)s[l]].end(), r);

    // printf("%d %d\n", l, r);
    while (*(--ptr) > l) {
        int p = *ptr;
        sol[l] = '(';
        sol[p] = ')';
        bool isPos = (solve(l + 1, p - 1) & solve(p + 1, r));
        if (isPos) {
            mp[l][r] = true;
            return true;
        }
    }

    mp[l][r] = false;
    return false;
}

int main() {
    int n;

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

    for (int i = 0; i < 26; i++)
        pos[i].push_back(-1);
    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...