5351 | 2023-04-26 10:48:03 | ZsofiaKeresztely | Zárójelek | cpp14 | Accepted 100/100 | 37ms | 7488 KiB |
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define fi first
#define se second
typedef long long ll;
int main()
{
int n;
cin >> n;
vector<pii> reql, reqr;
vector<int> dif(n+1), op(n+1, 0), opp(n);
for (int i=1; i<=n; i++){
string s;
cin >> s;
int left = 0, right = 0, need = 0;
for (char c : s){
if (c == '(') left++;
else right++;
if (left + need < right) need++;
}
dif[i] = left - right;
if (left > right){
reql.push_back({need, i});
}
else{
left = 0; right = 0; need = 0;
for (int i=s.size()-1; i>=0; i--){
if (s[i] == '(') left++;
else right++;
if (right + need < left) need++;
}
reqr.push_back({need, i});
}
}
reql.push_back({0, 0});
reqr.push_back({0, 0});
sort(reql.begin(), reql.end());
sort(reqr.begin(), reqr.end());
priority_queue<pii> pq;
int ind = 0, provl = 0, cnt = 1, provr = 0;
while (ind + 1 < reql.size() && !reql[ind+1].fi){
ind++;
pq.push({dif[reql[ind].se], reql[ind].se});
}
while (!pq.empty()){
pii p = pq.top();
pq.pop();
provl += p.fi;
op[p.se] = cnt;
cnt++;
while (ind + 1 < reql.size() && reql[ind+1].fi <= provl){
ind++;
pq.push({dif[reql[ind].se], reql[ind].se});
}
while (ind > 0 && reql[ind].fi > provl){
if (!op[reql[ind].se]){
cout << -1;
return 0;
}
ind--;
}
}
ind = 0;
cnt = n;
while (ind + 1 < reqr.size() && !reqr[ind+1].fi){
ind++;
pq.push({-1*dif[reqr[ind].se], reqr[ind].se});
}
while (!pq.empty()){
pii p = pq.top();
pq.pop();
provr += p.fi;
op[p.se] = cnt;
cnt--;
while (ind + 1 < reqr.size() && reqr[ind+1].fi <= provr){
ind++;
pq.push({-1*dif[reqr[ind].se], reqr[ind].se});
}
while (ind > 0 && reqr[ind].fi > provr){
if (!op[reqr[ind].se]){
cout << -1;
return 0;
}
ind--;
}
}
if (provl != provr){
cout << -1;
return 0;
}
for (int i=1; i<=n; i++){
if (!op[i]){
cout << -1;
return 0;
}
opp[op[i]-1] = i;
}
for (int x : opp){
cout << x << " ";
}
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 3ms | 1812 KiB | ||||
2 | Accepted | 9ms | 2220 KiB | ||||
subtask2 | 11/11 | ||||||
3 | Accepted | 3ms | 2200 KiB | ||||
4 | Accepted | 3ms | 2420 KiB | ||||
5 | Accepted | 3ms | 2504 KiB | ||||
6 | Accepted | 3ms | 2616 KiB | ||||
7 | Accepted | 8ms | 3200 KiB | ||||
8 | Accepted | 8ms | 3496 KiB | ||||
subtask3 | 6/6 | ||||||
9 | Accepted | 8ms | 3520 KiB | ||||
10 | Accepted | 8ms | 3720 KiB | ||||
11 | Accepted | 8ms | 3852 KiB | ||||
subtask4 | 14/14 | ||||||
12 | Accepted | 8ms | 3816 KiB | ||||
13 | Accepted | 8ms | 3804 KiB | ||||
subtask5 | 23/23 | ||||||
14 | Accepted | 8ms | 4080 KiB | ||||
15 | Accepted | 8ms | 4272 KiB | ||||
subtask6 | 19/19 | ||||||
16 | Accepted | 8ms | 4204 KiB | ||||
17 | Accepted | 9ms | 4308 KiB | ||||
18 | Accepted | 9ms | 4332 KiB | ||||
19 | Accepted | 8ms | 4516 KiB | ||||
20 | Accepted | 8ms | 4440 KiB | ||||
21 | Accepted | 7ms | 4488 KiB | ||||
22 | Accepted | 7ms | 4496 KiB | ||||
23 | Accepted | 7ms | 4492 KiB | ||||
24 | Accepted | 7ms | 4496 KiB | ||||
subtask7 | 27/27 | ||||||
25 | Accepted | 8ms | 4540 KiB | ||||
26 | Accepted | 10ms | 4816 KiB | ||||
27 | Accepted | 10ms | 4764 KiB | ||||
28 | Accepted | 12ms | 5084 KiB | ||||
29 | Accepted | 14ms | 5476 KiB | ||||
30 | Accepted | 37ms | 7488 KiB | ||||
31 | Accepted | 9ms | 5148 KiB | ||||
32 | Accepted | 10ms | 5180 KiB | ||||
33 | Accepted | 9ms | 4980 KiB | ||||
34 | Accepted | 12ms | 5192 KiB | ||||
35 | Accepted | 8ms | 4916 KiB | ||||
36 | Accepted | 12ms | 5292 KiB | ||||
37 | Accepted | 8ms | 4944 KiB | ||||
38 | Accepted | 8ms | 5012 KiB | ||||
39 | Accepted | 19ms | 6064 KiB | ||||
40 | Accepted | 6ms | 4972 KiB | ||||
41 | Accepted | 4ms | 4936 KiB | ||||
42 | Accepted | 8ms | 5276 KiB | ||||
43 | Accepted | 7ms | 5104 KiB |