#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 << " ";
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 4ms | 4008 KiB | ||||
2 | Accepted | 9ms | 4536 KiB | ||||
subtask2 | 11/11 | ||||||
3 | Accepted | 4ms | 4412 KiB | ||||
4 | Accepted | 3ms | 4512 KiB | ||||
5 | Accepted | 4ms | 4856 KiB | ||||
6 | Accepted | 3ms | 5064 KiB | ||||
7 | Accepted | 8ms | 5796 KiB | ||||
8 | Accepted | 8ms | 6056 KiB | ||||
subtask3 | 6/6 | ||||||
9 | Accepted | 9ms | 5664 KiB | ||||
10 | Accepted | 8ms | 5748 KiB | ||||
11 | Accepted | 9ms | 5772 KiB | ||||
subtask4 | 14/14 | ||||||
12 | Accepted | 9ms | 5928 KiB | ||||
13 | Accepted | 8ms | 5852 KiB | ||||
subtask5 | 23/23 | ||||||
14 | Accepted | 9ms | 6124 KiB | ||||
15 | Accepted | 8ms | 6104 KiB | ||||
subtask6 | 19/19 | ||||||
16 | Accepted | 8ms | 5892 KiB | ||||
17 | Accepted | 8ms | 5884 KiB | ||||
18 | Accepted | 8ms | 6324 KiB | ||||
19 | Accepted | 8ms | 6520 KiB | ||||
20 | Accepted | 9ms | 6608 KiB | ||||
21 | Accepted | 8ms | 6688 KiB | ||||
22 | Accepted | 8ms | 6656 KiB | ||||
23 | Accepted | 8ms | 6668 KiB | ||||
24 | Accepted | 8ms | 6888 KiB | ||||
subtask7 | 27/27 | ||||||
25 | Accepted | 8ms | 7044 KiB | ||||
26 | Accepted | 9ms | 7268 KiB | ||||
27 | Accepted | 9ms | 7484 KiB | ||||
28 | Accepted | 10ms | 7604 KiB | ||||
29 | Accepted | 14ms | 7832 KiB | ||||
30 | Accepted | 39ms | 9804 KiB | ||||
31 | Accepted | 10ms | 7496 KiB | ||||
32 | Accepted | 12ms | 7876 KiB | ||||
33 | Accepted | 10ms | 7672 KiB | ||||
34 | Accepted | 12ms | 7644 KiB | ||||
35 | Accepted | 8ms | 7428 KiB | ||||
36 | Accepted | 13ms | 7684 KiB | ||||
37 | Accepted | 8ms | 7364 KiB | ||||
38 | Accepted | 8ms | 7352 KiB | ||||
39 | Accepted | 20ms | 8304 KiB | ||||
40 | Accepted | 7ms | 7308 KiB | ||||
41 | Accepted | 4ms | 7268 KiB | ||||
42 | Accepted | 8ms | 7544 KiB | ||||
43 | Accepted | 8ms | 7296 KiB |