제출 #1221914

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1221914		LucaIlie	괄호 문자열 (CEOI16_match)	C++20	10 / 100	2093 ms	5704 KiB

match

#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)
            return true;
    }

    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;
}

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