101982024-03-29 12:27:50111Zárójelekcpp17Időlimit túllépés 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Időlimit túllépés526ms252156 KiB
2Időlimit túllépés504ms252352 KiB
subtask20/11
3Elfogadva495ms252312 KiB
4Elfogadva499ms252572 KiB
5Időlimit túllépés508ms252780 KiB
6Elfogadva497ms252788 KiB
7Időlimit túllépés503ms253504 KiB
8Időlimit túllépés500ms253564 KiB
subtask30/6
9Időlimit túllépés504ms253164 KiB
10Időlimit túllépés503ms253204 KiB
11Elfogadva500ms253416 KiB
subtask414/14
12Elfogadva500ms253496 KiB
13Elfogadva500ms253524 KiB
subtask50/23
14Időlimit túllépés504ms253616 KiB
15Hibás válasz500ms253504 KiB
subtask60/19
16Időlimit túllépés500ms253504 KiB
17Időlimit túllépés501ms253500 KiB
18Időlimit túllépés501ms253500 KiB
19Hibás válasz500ms253504 KiB
20Időlimit túllépés501ms253504 KiB
21Hibás válasz458ms253744 KiB
22Időlimit túllépés500ms253716 KiB
23Hibás válasz460ms253940 KiB
24Hibás válasz500ms253944 KiB
subtask70/27
25Időlimit túllépés503ms254092 KiB
26Időlimit túllépés504ms254092 KiB
27Időlimit túllépés508ms254084 KiB
28Hibás válasz462ms254200 KiB
29Időlimit túllépés515ms254364 KiB
30Időlimit túllépés561ms254456 KiB
31Időlimit túllépés507ms254504 KiB
32Hibás válasz462ms254568 KiB
33Hibás válasz456ms254688 KiB
34Időlimit túllépés507ms254660 KiB
35Hibás válasz456ms254900 KiB
36Hibás válasz460ms255136 KiB
37Elfogadva455ms255260 KiB
38Időlimit túllépés509ms255228 KiB
39Időlimit túllépés529ms255236 KiB
40Időlimit túllépés503ms255196 KiB
41Hibás válasz456ms255056 KiB
42Hibás válasz456ms255188 KiB
43Időlimit túllépés504ms255128 KiB