Submission #940259

#	Time	Username	Problem	Language	Result	Execution time	Memory
940259		thinknoexit	Match (CEOI16_match)	C++17	10 / 100	10 ms	456 KiB

match

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n;
string s;
int ans[22], a[22];
bool ch = 0;
void solve(int bit) {
    stack<char> st;
    for (int i = 0;i < n;i++) {
        a[i] = (bit >> i) & 1;
        if (a[i]) {
            if (st.empty()) return;
            if (st.top() != s[i]) return;
            st.pop();
        }
        else {
            st.push(s[i]);
        }
    }
    if (!st.empty()) return;
    for (int i = 0;i < n;i++) {
        if (ans[i] != a[i]) {
            if (ans[i] > a[i]) {
                for (int i = 0;i < n;i++) ans[i] = a[i];
            }
            break;
        }
    }
    ch = 1;
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    memset(ans, 0x3f, sizeof ans);
    cin >> s;
    n = s.size();
    for (int v = 0;v < (1 << n);v++) {
        solve(v);
    }
    if (!ch) cout << -1;
    else {
        for (int i = 0;i < n;i++) {
            cout << "()"[ans[i]];
        }
    }
    return 0;
}

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