Submission #1117701

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117701		vjudge1	Match (CEOI16_match)	C++17	10 / 100	971 ms	336 KiB

match

#include "bits/stdc++.h"

using namespace std;

const int mxN = 20;

int ar[mxN];

int main() {
    string S;
    cin >> S;

    int N = S.size();
    string ans(N, ')');

    for (int i = 0; i < (1 << N); i ++) {
        vector<int> match(N);
        stack<int> open;
        string bit;
        int balance = 0;
        int f = 1;
        for (int j = 0; j < N; j ++) {
            int bt = (i >> j) & 1;
            if (bt) {
                balance ++;
            } else {
                balance --;
            }
            if (0 > balance) {
                f = 0;
                break;
            }
            if (bt) {
                open.push(j);
                bit += '(';
            } else {
                match[open.top()] = j;
                match[j] = open.top();
                open.pop();
                bit += ')';
            }
        }
        if (!f || balance) {
            continue;
        }
        for (int j = 0; j < N; j ++) {
            int k = match[j];
            if (S[j] ^ S[k]) {
                f = 0;
            }
        }
        if (f) {
            ans = min(ans, bit);
        }
    }

    if (ans[0] != ')') {
        cout << ans << endl;
    } else {
        cout << -1 << endl;
    }
}

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