5012 2023. 04. 09 14:16:37 zsombor Zárójelek cpp17 Elfogadva 100/100 39ms 9804 KiB
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int val(string s) {
    int ret = 0;
    for (char ch : s) ret += (ch == '(' ? 1 : -1);
    return ret;
}

int cost1(string s) {
    int ret = 0, cur = 0;
    for (char ch : s) {
        cur += (ch == ')' ? 1 : -1);
        ret = max(ret, cur);
    }
    return ret;
}

int cost2(string s) {
    reverse(s.begin(), s.end());
    int ret = 0, cur = 0;
    for (char ch : s) {
        cur += (ch == '(' ? 1 : -1);
        ret = max(ret, cur);
    }
    return ret;
}

vector <int> solve(vector <pair <pair<int, int>, int>>& V) {
    int sum = 0, nxt = 0;
    priority_queue <pair <int, int>> pq;
    vector <int> ret;
    sort(V.begin(), V.end());

    while (true) {
        while (nxt<V.size() && V[nxt].first.first <= sum) {
            pq.push({ V[nxt].first.second,V[nxt].second });
            nxt++;
        }
        if (pq.empty()) break;
        sum += pq.top().first;
        ret.push_back(pq.top().second);
        pq.pop();
    }

    if (ret.size() < V.size()) { cout << -1; exit(0); }
    return ret;
}

int main()
{
    int n;
    string s;
    vector <int> v(1e5 + 1, 0);
    vector <int> c1(1e5 + 1, 0);
    vector <int> c2(1e5 + 1, 0);
    vector <pair <pair<int, int>, int>> V1;
    vector <pair <pair<int, int>, int>> V2;

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        v[i] = val(s);
        c1[i] = cost1(s);
        c2[i] = cost2(s);
        if (v[i] >= 0) V1.push_back({ {c1[i],v[i]},i });
        if (v[i] < 0) V2.push_back({ {c2[i],-v[i]},i });
    }

    vector <int> ans = solve(V1);
    vector <int> ans2 = solve(V2);
    reverse(ans2.begin(), ans2.end());
    for (int i : ans2) ans.push_back(i);

    int sum = 0;
    for (int i : ans) {
        if (c1[i] > sum) { cout << -1; return 0; }
        sum += v[i];
    }
    if (sum) { cout << -1; return 0; }
    for (int i : ans) cout << i << " ";
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 4ms 4008 KiB
2 Elfogadva 9ms 4536 KiB
subtask2 11/11
3 Elfogadva 4ms 4412 KiB
4 Elfogadva 3ms 4512 KiB
5 Elfogadva 4ms 4856 KiB
6 Elfogadva 3ms 5064 KiB
7 Elfogadva 8ms 5796 KiB
8 Elfogadva 8ms 6056 KiB
subtask3 6/6
9 Elfogadva 9ms 5664 KiB
10 Elfogadva 8ms 5748 KiB
11 Elfogadva 9ms 5772 KiB
subtask4 14/14
12 Elfogadva 9ms 5928 KiB
13 Elfogadva 8ms 5852 KiB
subtask5 23/23
14 Elfogadva 9ms 6124 KiB
15 Elfogadva 8ms 6104 KiB
subtask6 19/19
16 Elfogadva 8ms 5892 KiB
17 Elfogadva 8ms 5884 KiB
18 Elfogadva 8ms 6324 KiB
19 Elfogadva 8ms 6520 KiB
20 Elfogadva 9ms 6608 KiB
21 Elfogadva 8ms 6688 KiB
22 Elfogadva 8ms 6656 KiB
23 Elfogadva 8ms 6668 KiB
24 Elfogadva 8ms 6888 KiB
subtask7 27/27
25 Elfogadva 8ms 7044 KiB
26 Elfogadva 9ms 7268 KiB
27 Elfogadva 9ms 7484 KiB
28 Elfogadva 10ms 7604 KiB
29 Elfogadva 14ms 7832 KiB
30 Elfogadva 39ms 9804 KiB
31 Elfogadva 10ms 7496 KiB
32 Elfogadva 12ms 7876 KiB
33 Elfogadva 10ms 7672 KiB
34 Elfogadva 12ms 7644 KiB
35 Elfogadva 8ms 7428 KiB
36 Elfogadva 13ms 7684 KiB
37 Elfogadva 8ms 7364 KiB
38 Elfogadva 8ms 7352 KiB
39 Elfogadva 20ms 8304 KiB
40 Elfogadva 7ms 7308 KiB
41 Elfogadva 4ms 7268 KiB
42 Elfogadva 8ms 7544 KiB
43 Elfogadva 8ms 7296 KiB