Submission #619924

#	Time	Username	Problem	Language	Result	Execution time	Memory
619924		errorgorn	Superpozicija (COCI22_superpozicija)	C++17	110 / 110	239 ms	52848 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

struct node{
	int s,e,m;
	int val=0,lazy=0;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void propo(){
		if (lazy){
			val+=lazy;
			
			if (s!=e){
				l->lazy+=lazy;
				r->lazy+=lazy;
			}
			
			lazy=0;
		}
	}
	
	void update(int i,int j,int k){
		if (s==i && e==j) lazy+=k;
		else{
			if (j<=m) l->update(i,j,k);
			else if (m<i) r->update(i,j,k);
			else l->update(i,m,k),r->update(m+1,j,k);
			
			l->propo(),r->propo();
			val=min(l->val,r->val);
		}
	}
	
	int query(int i,int j){
		propo();
		
		if (s==i && e==j) return val;
		else if (j<=m) return l->query(i,j);
		else if (m<i) return r->query(i,j);
		else return min(l->query(i,m),r->query(m+1,j));
	}
	
	int find(){
		propo();
		
		if (s==e) return s;
		
		l->propo(),r->propo();
		if (l->val<0) return l->find();
		else return r->find();
	}
} *root;

struct node2{
	int s,e,m;
	ii val;
	node2 *l,*r;
	
	node2 (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		val=ii(1e9,-1);
		if (s!=e){
			l=new node2(s,m);
			r=new node2(m+1,e);
		}
	}
	
	void update(int i,ii k){
		if (s==e) val=k;
		else{
			if (i<=m) l->update(i,k);
			else r->update(i,k);
			
			val=min(l->val,r->val);
		}
	}
	
	ii query(int i,int j){
		if (s==i && e==j) return val;
		else if (j<=m) return l->query(i,j);
		else if (m<i) return r->query(i,j);
		else return min(l->query(i,m),r->query(m+1,j));
	}
} *root2;

int n;
string s;
ii arr[100005];
int ans[100005];

signed main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	int TC;
	cin>>TC;
	while (TC--){
		cin>>n;
		cin>>s;
		rep(x,0,n){
			cin>>arr[x].fi>>arr[x].se;
			arr[x].fi--,arr[x].se--;
		}
		
		if (n%2==1){
			cout<<"-1"<<endl;
			continue;
		}
		
		root=new node(0,2*n);
		root2=new node2(0,2*n);
		
		int num=0;
		rep(x,0,n){
			if (s[arr[x].fi]==s[arr[x].se]){
				if (s[arr[x].fi]=='('){
					ans[x]=0;
					root->update(arr[x].fi,2*n,1);
				}
				else{
					ans[x]=1;
					root->update(arr[x].se,2*n,-1);
				}
			}
			else{
				if (s[arr[x].fi]==')'){
					ans[x]=0;
					root->update(arr[x].fi,2*n,-1);
				}
				else{
					ans[x]=1;
					root->update(arr[x].se,2*n,-1);
				}
				
				num++;
				root2->update(arr[x].fi,{arr[x].se,x});
			}
		}
		
		int tot=root->query(2*n,2*n);
		
		if (tot>0 || tot<-2*num){
			cout<<"-1"<<endl;
			continue;
		}
		
		bool bad=false;
		while (root->query(2*n,2*n)){
			int pos=root->find();
			ii temp=root2->query(0,2*n);
			
			//cout<<temp.fi<<" "<<temp.se<<endl;
			
			int x;
			if (temp.fi<=pos){
				x=temp.se;
			}
			else{
				temp=root2->query(0,pos);
				if (temp.fi==1e9){
					bad=true;
					break;
				}
				
				x=temp.se;
				
			}
			
			root->update(arr[x].fi,2*n,1);
			root->update(arr[x].se,2*n,1);
			root2->update(arr[x].fi,{1e9,-1});
			ans[x]^=1;
		}
		
		if (bad || root->query(0,2*n)<0){
			cout<<"-1"<<endl;
			continue;
		}
		
		rep(x,0,n) cout<<ans[x]<<" "; cout<<endl;
	}
}

Compilation message (stderr)

Main.cpp: In constructor 'node::node(long long int, long long int)':
Main.cpp:30:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~
Main.cpp: In constructor 'node2::node2(long long int, long long int)':
Main.cpp:89:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~
Main.cpp: In function 'int main()':
Main.cpp:18:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   18 | #define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e)?x++:x--))
      |                    ^~~
Main.cpp:211:3: note: in expansion of macro 'rep'
  211 |   rep(x,0,n) cout<<ans[x]<<" "; cout<<endl;
      |   ^~~
Main.cpp:211:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  211 |   rep(x,0,n) cout<<ans[x]<<" "; cout<<endl;
      |                                 ^~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 70 / 70