Submission #1221800

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221800		LucaIlie	Match (CEOI16_match)	C++20	10 / 100	0 ms	328 KiB

match

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

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