Submission #476692

#	Time	Username	Problem	Language	Result	Execution time	Memory
476692		wiktoria_bazan	Match (CEOI16_match)	C++14	10 / 100	90 ms	268 KiB

match

#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;

int n;
string s;
stack <int> S;

void generuj() {
    bool t = true;
    string a = "";
    string w = "))))))))))))))))))";
    for (int bitmask = 1 << (n-1); bitmask < (1 << n); bitmask++) {
        a.clear();
        t = true;
        for (int i = n - 1; i >= 0; i--) {
            if (bitmask & (1 << i)) {
                S.push(n - i - 1);
                a.insert(a.size(), "(");
            }
            else {
                a.insert(a.size(), ")");
                if (S.empty()) {
                    t = false;
                    break;
                }
                int v = S.top();
                S.pop();
                if (s[v] != s[n - i - 1]) {
                    t = false;
                    break;
                }
            }
        }
        if (S.empty() && t == true) {
            w = min(w, a);
        }
        while (!S.empty()) S.pop();
    }
    if (w == "))))))))))))))))))") {
        cout << -1;
        return;
    }
    cout << w;
}

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

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