#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MZ 500000
struct ST{
int n;
vector<int>a,b;
ST(int n):n(n),a(n*4,INT_MIN),b(n*4,-1){
}
pair<int,int>query(int i,int l,int r,int ll,int rr){
if(l>rr||r<ll){
return {INT_MIN,-1};
}
if(l>=ll&&r<=rr){
return {a[i],b[i]};
}
auto[al,bl]=query(i*2+1,l,(l+r)/2,ll,rr);
auto[ar,br]=query(i*2+2,(l+r)/2+1,r,ll,rr);
return al>=ar?pair<int,int>{al,bl}:pair<int,int>{ar,br};
}
pair<int,int>query(int ll,int rr){
return query(0,0,n-1,ll,rr);
}
void update(int i,int l,int r,int ii,int xx){
if(l>ii||r<ii){
return;
}
if(l==r){
a[i]=xx;
b[i]=l;
return;
}
update(i*2+1,l,(l+r)/2,ii,xx);
update(i*2+2,(l+r)/2+1,r,ii,xx);
a[i]=a[i*2+1]>=a[i*2+2]?a[i*2+1]:a[i*2+2];
b[i]=a[i*2+1]>=a[i*2+2]?b[i*2+1]:b[i*2+2];
}
void update(int ii,int xx){
update(0,0,n-1,ii,xx);
}
};
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin>>N;
ST a(MZ),b(MZ);
vector<int>ma(MZ),mb(MZ),za(MZ),zb(MZ);
set<int>aa,bb;
for(int i=0;i<MZ;i++){
aa.insert(i);
bb.insert(i);
}
int x=0,c=0;
for(int i=0;i<N;i++){
string S;
cin>>S;
int y=0,z=0;
for(char c:S){
if(c=='('){
y++;
}
else{
y--;
z=max(z,-y);
}
}
x+=y;
if(y>=0){
c++;
int zz=*aa.lower_bound(MZ/2-z);
aa.erase(zz);
a.update(zz,y);
ma[zz]=i;
za[zz]=z;
}
else{
int zz=*bb.lower_bound(MZ/2-z);
bb.erase(zz);
b.update(zz,y+z);
mb[zz]=i;
zb[zz]=z;
}
}
if(x!=0){
cout<<-1<<'\n';
return 0;
}
vector<int>ans;
while(ans.size()<N){
if(c>0){
c--;
auto[y,z]=a.query(MZ/2-x,MZ-1);
if(y==INT_MIN){
cout<<-1<<'\n';
return 0;
}
a.update(z,INT_MIN);
x+=y;
if(x<0)exit(1);
ans.push_back(ma[z]);
}
else{
auto[yz,z]=b.query(MZ/2-x,MZ-1);
if(yz==INT_MIN){
cout<<-1<<'\n';
return 0;
}
b.update(z,INT_MIN);
x+=yz-zb[z];
if(x<0)exit(1);
ans.push_back(mb[z]);
}
}
if(x!=0)exit(1);
for(int i:ans){
cout<<i+1<<' ';
}
cout<<'\n';
return 0;
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Time limit exceeded | 526ms | 252156 KiB | ||||
2 | Time limit exceeded | 504ms | 252352 KiB | ||||
subtask2 | 0/11 | ||||||
3 | Accepted | 495ms | 252312 KiB | ||||
4 | Accepted | 499ms | 252572 KiB | ||||
5 | Time limit exceeded | 508ms | 252780 KiB | ||||
6 | Accepted | 497ms | 252788 KiB | ||||
7 | Time limit exceeded | 503ms | 253504 KiB | ||||
8 | Time limit exceeded | 500ms | 253564 KiB | ||||
subtask3 | 0/6 | ||||||
9 | Time limit exceeded | 504ms | 253164 KiB | ||||
10 | Time limit exceeded | 503ms | 253204 KiB | ||||
11 | Accepted | 500ms | 253416 KiB | ||||
subtask4 | 14/14 | ||||||
12 | Accepted | 500ms | 253496 KiB | ||||
13 | Accepted | 500ms | 253524 KiB | ||||
subtask5 | 0/23 | ||||||
14 | Time limit exceeded | 504ms | 253616 KiB | ||||
15 | Wrong answer | 500ms | 253504 KiB | ||||
subtask6 | 0/19 | ||||||
16 | Time limit exceeded | 500ms | 253504 KiB | ||||
17 | Time limit exceeded | 501ms | 253500 KiB | ||||
18 | Time limit exceeded | 501ms | 253500 KiB | ||||
19 | Wrong answer | 500ms | 253504 KiB | ||||
20 | Time limit exceeded | 501ms | 253504 KiB | ||||
21 | Wrong answer | 458ms | 253744 KiB | ||||
22 | Time limit exceeded | 500ms | 253716 KiB | ||||
23 | Wrong answer | 460ms | 253940 KiB | ||||
24 | Wrong answer | 500ms | 253944 KiB | ||||
subtask7 | 0/27 | ||||||
25 | Time limit exceeded | 503ms | 254092 KiB | ||||
26 | Time limit exceeded | 504ms | 254092 KiB | ||||
27 | Time limit exceeded | 508ms | 254084 KiB | ||||
28 | Wrong answer | 462ms | 254200 KiB | ||||
29 | Time limit exceeded | 515ms | 254364 KiB | ||||
30 | Time limit exceeded | 561ms | 254456 KiB | ||||
31 | Time limit exceeded | 507ms | 254504 KiB | ||||
32 | Wrong answer | 462ms | 254568 KiB | ||||
33 | Wrong answer | 456ms | 254688 KiB | ||||
34 | Time limit exceeded | 507ms | 254660 KiB | ||||
35 | Wrong answer | 456ms | 254900 KiB | ||||
36 | Wrong answer | 460ms | 255136 KiB | ||||
37 | Accepted | 455ms | 255260 KiB | ||||
38 | Time limit exceeded | 509ms | 255228 KiB | ||||
39 | Time limit exceeded | 529ms | 255236 KiB | ||||
40 | Time limit exceeded | 503ms | 255196 KiB | ||||
41 | Wrong answer | 456ms | 255056 KiB | ||||
42 | Wrong answer | 456ms | 255188 KiB | ||||
43 | Time limit exceeded | 504ms | 255128 KiB |