10198 2024. 03. 29 12:27:50 111 Zárójelek cpp17 Időlimit túllépés 14/100 561ms 255260 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 Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Időlimit túllépés 526ms 252156 KiB
2 Időlimit túllépés 504ms 252352 KiB
subtask2 0/11
3 Elfogadva 495ms 252312 KiB
4 Elfogadva 499ms 252572 KiB
5 Időlimit túllépés 508ms 252780 KiB
6 Elfogadva 497ms 252788 KiB
7 Időlimit túllépés 503ms 253504 KiB
8 Időlimit túllépés 500ms 253564 KiB
subtask3 0/6
9 Időlimit túllépés 504ms 253164 KiB
10 Időlimit túllépés 503ms 253204 KiB
11 Elfogadva 500ms 253416 KiB
subtask4 14/14
12 Elfogadva 500ms 253496 KiB
13 Elfogadva 500ms 253524 KiB
subtask5 0/23
14 Időlimit túllépés 504ms 253616 KiB
15 Hibás válasz 500ms 253504 KiB
subtask6 0/19
16 Időlimit túllépés 500ms 253504 KiB
17 Időlimit túllépés 501ms 253500 KiB
18 Időlimit túllépés 501ms 253500 KiB
19 Hibás válasz 500ms 253504 KiB
20 Időlimit túllépés 501ms 253504 KiB
21 Hibás válasz 458ms 253744 KiB
22 Időlimit túllépés 500ms 253716 KiB
23 Hibás válasz 460ms 253940 KiB
24 Hibás válasz 500ms 253944 KiB
subtask7 0/27
25 Időlimit túllépés 503ms 254092 KiB
26 Időlimit túllépés 504ms 254092 KiB
27 Időlimit túllépés 508ms 254084 KiB
28 Hibás válasz 462ms 254200 KiB
29 Időlimit túllépés 515ms 254364 KiB
30 Időlimit túllépés 561ms 254456 KiB
31 Időlimit túllépés 507ms 254504 KiB
32 Hibás válasz 462ms 254568 KiB
33 Hibás válasz 456ms 254688 KiB
34 Időlimit túllépés 507ms 254660 KiB
35 Hibás válasz 456ms 254900 KiB
36 Hibás válasz 460ms 255136 KiB
37 Elfogadva 455ms 255260 KiB
38 Időlimit túllépés 509ms 255228 KiB
39 Időlimit túllépés 529ms 255236 KiB
40 Időlimit túllépés 503ms 255196 KiB
41 Hibás válasz 456ms 255056 KiB
42 Hibás válasz 456ms 255188 KiB
43 Időlimit túllépés 504ms 255128 KiB