116252024-11-01 12:39:27MagyarKendeSZLGBob Baba Zárójelsorozatacpp17Time limit exceeded 50/100606ms84384 KiB
#include <cassert>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
using ll = long long;

int main() {
    cin.tie(0), ios::sync_with_stdio(0);

    int N;
    cin >> N;
    vector<int> a(N);
    for (int& x : a) cin >> x;

    // for (int x : a) cout << x << " ";
    // cout << "\n\n";

    unordered_set<int> s;
    s.insert(a[0]);

    vector<unordered_map<int, int>> pathS(N);
    pathS[0][a[0]] = 0;

    for (int i = 1; i < N; i++) {
        unordered_set<int> ns;
        for (int x : s) {
            ns.insert(x + a[i]);
            pathS[i][x + a[i]] = x;

            if (x - a[i] >= 0) {
                ns.insert(x - a[i]);
                pathS[i][x - a[i]] = x;
            }
        }
        swap(s, ns);
    }

    // for (int i = 0; i < N; i++) {
    //     cout << i << ":\n";
    //     for (auto [k, v] : pathS[i]) {
    //         cout << k << " " << v << "\n";
    //     }
    //     cout << "\n";
    // }

    for (int x : s) {
        if (!x) {
            vector<int> result(N);
            for (int i = N - 1; i >= 0; i--) {
                result[i] = x - pathS[i][x];
                x = pathS[i][x];
            }

            for (int x : result) {
                cout << string(abs(x), "()"[x < 0]);
            }
            cout << "\n";

            exit(0);
        }
    }

    cout << "-1\n";
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms320 KiB
2Accepted1ms320 KiB
3Accepted1ms500 KiB
subtask220/20
4Accepted1ms320 KiB
5Accepted1ms320 KiB
6Accepted1ms320 KiB
subtask330/30
7Accepted1ms436 KiB
8Accepted1ms320 KiB
9Accepted1ms320 KiB
10Accepted1ms588 KiB
11Accepted1ms320 KiB
subtask40/50
12Time limit exceeded606ms82416 KiB
13Time limit exceeded606ms84384 KiB
14Time limit exceeded606ms81848 KiB
15Time limit exceeded606ms84224 KiB
16Time limit exceeded578ms79684 KiB
17Time limit exceeded583ms80848 KiB
18Time limit exceeded578ms75952 KiB
19Time limit exceeded584ms74064 KiB
20Time limit exceeded588ms76884 KiB
21Time limit exceeded588ms74244 KiB
22Time limit exceeded588ms75504 KiB
23Time limit exceeded588ms77816 KiB
24Time limit exceeded504ms54364 KiB
25Accepted500ms58712 KiB
26Accepted488ms60248 KiB
27Time limit exceeded588ms58456 KiB
28Accepted458ms50008 KiB
29Accepted458ms50264 KiB
30Accepted246ms26148 KiB
31Accepted204ms25936 KiB
32Accepted200ms25432 KiB
33Accepted275ms28248 KiB
34Accepted177ms21412 KiB
35Accepted225ms23680 KiB
36Accepted207ms26008 KiB
37Accepted89ms11864 KiB
38Accepted221ms27736 KiB
39Accepted483ms51440 KiB
40Time limit exceeded592ms69448 KiB
41Time limit exceeded603ms66120 KiB
42Time limit exceeded587ms68184 KiB
43Time limit exceeded588ms65492 KiB
44Time limit exceeded587ms71536 KiB
45Time limit exceeded606ms72280 KiB
46Time limit exceeded582ms74220 KiB
47Time limit exceeded588ms73968 KiB
48Time limit exceeded584ms76208 KiB
49Time limit exceeded605ms77984 KiB
50Time limit exceeded587ms77712 KiB
51Time limit exceeded596ms76528 KiB
52Time limit exceeded560ms70096 KiB
53Accepted393ms50700 KiB
54Time limit exceeded592ms76552 KiB
55Time limit exceeded583ms79088 KiB
56Time limit exceeded592ms77788 KiB
57Time limit exceeded591ms78068 KiB
58Time limit exceeded596ms76784 KiB