50122023-04-09 14:16:37zsomborZárójelekcpp17Accepted 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 << " ";
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted4ms4008 KiB
2Accepted9ms4536 KiB
subtask211/11
3Accepted4ms4412 KiB
4Accepted3ms4512 KiB
5Accepted4ms4856 KiB
6Accepted3ms5064 KiB
7Accepted8ms5796 KiB
8Accepted8ms6056 KiB
subtask36/6
9Accepted9ms5664 KiB
10Accepted8ms5748 KiB
11Accepted9ms5772 KiB
subtask414/14
12Accepted9ms5928 KiB
13Accepted8ms5852 KiB
subtask523/23
14Accepted9ms6124 KiB
15Accepted8ms6104 KiB
subtask619/19
16Accepted8ms5892 KiB
17Accepted8ms5884 KiB
18Accepted8ms6324 KiB
19Accepted8ms6520 KiB
20Accepted9ms6608 KiB
21Accepted8ms6688 KiB
22Accepted8ms6656 KiB
23Accepted8ms6668 KiB
24Accepted8ms6888 KiB
subtask727/27
25Accepted8ms7044 KiB
26Accepted9ms7268 KiB
27Accepted9ms7484 KiB
28Accepted10ms7604 KiB
29Accepted14ms7832 KiB
30Accepted39ms9804 KiB
31Accepted10ms7496 KiB
32Accepted12ms7876 KiB
33Accepted10ms7672 KiB
34Accepted12ms7644 KiB
35Accepted8ms7428 KiB
36Accepted13ms7684 KiB
37Accepted8ms7364 KiB
38Accepted8ms7352 KiB
39Accepted20ms8304 KiB
40Accepted7ms7308 KiB
41Accepted4ms7268 KiB
42Accepted8ms7544 KiB
43Accepted8ms7296 KiB