oj.uz

Submission #619924

# Submission time Handle Problem Language Result Execution time Memory
619924 2022-08-02T17:15:24 Z errorgorn Superpozicija (COCI22_superpozicija) C++17
110 / 110
 239 ms 52848 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 52848 KB Output is correct
2 Correct 14 ms 984 KB Output is correct
3 Correct 80 ms 52556 KB Output is correct
4 Correct 102 ms 52460 KB Output is correct
5 Correct 86 ms 52476 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 51368 KB Output is correct
2 Correct 110 ms 47156 KB Output is correct
3 Correct 93 ms 42120 KB Output is correct
4 Correct 120 ms 47376 KB Output is correct
5 Correct 119 ms 42556 KB Output is correct
6 Correct 74 ms 27296 KB Output is correct
7 Correct 92 ms 32676 KB Output is correct
8 Correct 95 ms 38168 KB Output is correct
9 Correct 131 ms 43480 KB Output is correct
10 Correct 133 ms 48920 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 852 KB Output is correct
2 Correct 94 ms 51400 KB Output is correct
3 Correct 104 ms 47308 KB Output is correct
4 Correct 87 ms 42120 KB Output is correct
5 Correct 99 ms 47520 KB Output is correct
6 Correct 92 ms 42728 KB Output is correct
7 Correct 42 ms 27264 KB Output is correct
8 Correct 69 ms 32764 KB Output is correct
9 Correct 74 ms 38120 KB Output is correct
10 Correct 97 ms 43672 KB Output is correct
11 Correct 110 ms 49112 KB Output is correct

Subtask #4
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 52848 KB Output is correct
2 Correct 14 ms 984 KB Output is correct
3 Correct 80 ms 52556 KB Output is correct
4 Correct 102 ms 52460 KB Output is correct
5 Correct 86 ms 52476 KB Output is correct
6 Correct 92 ms 51368 KB Output is correct
7 Correct 110 ms 47156 KB Output is correct
8 Correct 93 ms 42120 KB Output is correct
9 Correct 120 ms 47376 KB Output is correct
10 Correct 119 ms 42556 KB Output is correct
11 Correct 74 ms 27296 KB Output is correct
12 Correct 92 ms 32676 KB Output is correct
13 Correct 95 ms 38168 KB Output is correct
14 Correct 131 ms 43480 KB Output is correct
15 Correct 133 ms 48920 KB Output is correct
16 Correct 2 ms 852 KB Output is correct
17 Correct 94 ms 51400 KB Output is correct
18 Correct 104 ms 47308 KB Output is correct
19 Correct 87 ms 42120 KB Output is correct
20 Correct 99 ms 47520 KB Output is correct
21 Correct 92 ms 42728 KB Output is correct
22 Correct 42 ms 27264 KB Output is correct
23 Correct 69 ms 32764 KB Output is correct
24 Correct 74 ms 38120 KB Output is correct
25 Correct 97 ms 43672 KB Output is correct
26 Correct 110 ms 49112 KB Output is correct
27 Correct 91 ms 51532 KB Output is correct
28 Correct 144 ms 47340 KB Output is correct
29 Correct 168 ms 42216 KB Output is correct
30 Correct 208 ms 47612 KB Output is correct
31 Correct 172 ms 42652 KB Output is correct
32 Correct 123 ms 27440 KB Output is correct
33 Correct 162 ms 32780 KB Output is correct
34 Correct 194 ms 38324 KB Output is correct
35 Correct 206 ms 43736 KB Output is correct
36 Correct 239 ms 49112 KB Output is correct