Submission #1294102

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294102		dragonrobot	Match (CEOI16_match)	C++17	0 / 100	0 ms	332 KiB

match

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s; cin >> s;
    int n = s.length();
    if (n % 2 != 0) { cout << -1; return 0; }

    vector<int> v(n, -1);
    vector<stack<int>> c(26);
    for (int i = 0; i < n; i++) {
        int x = s[i] - 'a';
        if (c[x].empty()) c[x].push(i);
        else { int j = c[x].top(); c[x].pop(); v[i] = j; v[j] = i; }
    }

    for (int i = 0; i < 26; i++) if (!c[i].empty()) { cout << -1; return 0; }

    map<pair<int,int>, string> m;
    auto f = [&](auto&& self, int i, int j) -> string {
        if (i > j) return "";
        if (m.count({i,j})) return m[{i,j}];

        string a = "-1";
        if (v[i] == j) { string t = self(self, i+1, j-1); if (t != "-1") a = "(" + t + ")"; }

        string b = "-1";
        int k = v[i];
        if (k < j) { string l = self(self, i, k); string r = self(self, k+1, j); 
            if (l != "-1" && r != "-1") { string t = l + r; if (b == "-1" || t < b) b = t; } 
        }

        string r = "-1";
        if (a != "-1") r = a;
        if (b != "-1" && (r == "-1" || b < r)) r = b;
        return m[{i,j}] = r;
    };

    cout << f(f, 0, n-1);
}

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