101982024-03-29 12:27:50111Zárójelekcpp17Time limit exceeded 14/100561ms255260 KiB
#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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Time limit exceeded526ms252156 KiB
2Time limit exceeded504ms252352 KiB
subtask20/11
3Accepted495ms252312 KiB
4Accepted499ms252572 KiB
5Time limit exceeded508ms252780 KiB
6Accepted497ms252788 KiB
7Time limit exceeded503ms253504 KiB
8Time limit exceeded500ms253564 KiB
subtask30/6
9Time limit exceeded504ms253164 KiB
10Time limit exceeded503ms253204 KiB
11Accepted500ms253416 KiB
subtask414/14
12Accepted500ms253496 KiB
13Accepted500ms253524 KiB
subtask50/23
14Time limit exceeded504ms253616 KiB
15Wrong answer500ms253504 KiB
subtask60/19
16Time limit exceeded500ms253504 KiB
17Time limit exceeded501ms253500 KiB
18Time limit exceeded501ms253500 KiB
19Wrong answer500ms253504 KiB
20Time limit exceeded501ms253504 KiB
21Wrong answer458ms253744 KiB
22Time limit exceeded500ms253716 KiB
23Wrong answer460ms253940 KiB
24Wrong answer500ms253944 KiB
subtask70/27
25Time limit exceeded503ms254092 KiB
26Time limit exceeded504ms254092 KiB
27Time limit exceeded508ms254084 KiB
28Wrong answer462ms254200 KiB
29Time limit exceeded515ms254364 KiB
30Time limit exceeded561ms254456 KiB
31Time limit exceeded507ms254504 KiB
32Wrong answer462ms254568 KiB
33Wrong answer456ms254688 KiB
34Time limit exceeded507ms254660 KiB
35Wrong answer456ms254900 KiB
36Wrong answer460ms255136 KiB
37Accepted455ms255260 KiB
38Time limit exceeded509ms255228 KiB
39Time limit exceeded529ms255236 KiB
40Time limit exceeded503ms255196 KiB
41Wrong answer456ms255056 KiB
42Wrong answer456ms255188 KiB
43Time limit exceeded504ms255128 KiB