oj.uz

Submission #1117701

# Submission time Handle Problem Language Result Execution time Memory
1117701 2024-11-24T07:37:10 Z vjudge1 Match (CEOI16_match) C++17
10 / 100
 971 ms 336 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 18 ms 336 KB Output is correct
3 Correct 5 ms 336 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 18 ms 336 KB Output is correct
3 Correct 5 ms 336 KB Output is correct
4 Incorrect 971 ms 336 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 18 ms 336 KB Output is correct
3 Correct 5 ms 336 KB Output is correct
4 Incorrect 971 ms 336 KB Output isn't correct
5 Halted 0 ms 0 KB -