50122023-04-09 14:16:37zsomborZárójelekcpp17Elfogadva 100/10039ms9804 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva4ms4008 KiB
2Elfogadva9ms4536 KiB
subtask211/11
3Elfogadva4ms4412 KiB
4Elfogadva3ms4512 KiB
5Elfogadva4ms4856 KiB
6Elfogadva3ms5064 KiB
7Elfogadva8ms5796 KiB
8Elfogadva8ms6056 KiB
subtask36/6
9Elfogadva9ms5664 KiB
10Elfogadva8ms5748 KiB
11Elfogadva9ms5772 KiB
subtask414/14
12Elfogadva9ms5928 KiB
13Elfogadva8ms5852 KiB
subtask523/23
14Elfogadva9ms6124 KiB
15Elfogadva8ms6104 KiB
subtask619/19
16Elfogadva8ms5892 KiB
17Elfogadva8ms5884 KiB
18Elfogadva8ms6324 KiB
19Elfogadva8ms6520 KiB
20Elfogadva9ms6608 KiB
21Elfogadva8ms6688 KiB
22Elfogadva8ms6656 KiB
23Elfogadva8ms6668 KiB
24Elfogadva8ms6888 KiB
subtask727/27
25Elfogadva8ms7044 KiB
26Elfogadva9ms7268 KiB
27Elfogadva9ms7484 KiB
28Elfogadva10ms7604 KiB
29Elfogadva14ms7832 KiB
30Elfogadva39ms9804 KiB
31Elfogadva10ms7496 KiB
32Elfogadva12ms7876 KiB
33Elfogadva10ms7672 KiB
34Elfogadva12ms7644 KiB
35Elfogadva8ms7428 KiB
36Elfogadva13ms7684 KiB
37Elfogadva8ms7364 KiB
38Elfogadva8ms7352 KiB
39Elfogadva20ms8304 KiB
40Elfogadva7ms7308 KiB
41Elfogadva4ms7268 KiB
42Elfogadva8ms7544 KiB
43Elfogadva8ms7296 KiB