oj.uz

Submission #968474

# Submission time Handle Problem Language Result Execution time Memory
968474 2024-04-23T13:00:16 Z Isam Superpozicija (COCI22_superpozicija) C++17
10 / 110
 26 ms 9016 KB 
#include<bits/stdc++.h>
using namespace std;

int n, l[1000100], r[1000100];

string z;

int ans[1000100];

set<pair<int, int>> pq;

set<int> st;

vector<int> tmp;

vector<pair<int, int>> v;

inline bool makni(int pos){
	
	auto it = st.lower_bound(pos);
	
	if(it == st.end()) return 0;
	
	st.erase(it);
	
	return 1;
	
}


signed main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	function<void()> test_case = [](){
		cin >> n >> z;
		
		z = '.' + z;
		
		st.clear(), pq.clear(), v.clear(), tmp.clear();
		
		for(register int i = 1; i <= n; ++i){
			cin >> l[i] >> r[i];
			
			if(z[l[i]] == '(' && z[r[i]] == '('){
				tmp.emplace_back(l[i]);
				
				ans[i] = 0;
				
				
			}else if(z[l[i]] == ')' && z[r[i]] == ')'){
				st.insert(r[i]);
				
				ans[i] = 1;
				
			}else if(z[l[i]] == '(' && z[r[i]] == ')'){
				st.insert(r[i]);
				
				v.emplace_back(pair<int, int>{l[i], i});
				
				ans[i] = 1;
				
			}else{
				
				st.insert(l[i]);
				
				v.emplace_back(pair<int, int>{l[i], i});
				
				ans[l[i]] = 0;
				
			}
			
			
			
			
		}
		
	//	if(n & 1) return cout << -1 << '\n', void();
		
		for(auto to : tmp){
			
			if(!makni(to)) return cout << -1 << '\n', void();
			
			
		}
		
		
		sort(v.begin(), v.end());
		
		int p = -1;
		
		while(!st.empty()){
			int lim = *st.begin();
			
			while(p + 1 < (int)v.size() && v[p+1].first <= lim){
				p++;
				
				int ind = v[p].second;
				
				pq.insert({r[ind], ind});
				
			}
			
			if(pq.empty()) return cout << -1 << '\n', void();
			
			int ind = pq.begin()->second;
			
			pq.erase(pq.begin());
			
			ans[ind] ^= 1;
			
			if(!makni(l[ind])) return cout << -1 << '\n', void();
			
			if(!makni(r[ind])) return cout << -1 << '\n', void();
			
			
		}
		

		for(register int i = 1; i <= n; ++i){
			 cout << ans[i] << " \n"[i==n];
		}
		
		
		
		
		
	};
	while(T--) test_case();
	return 0;
}

Compilation message

Main.cpp: In lambda function:
Main.cpp:42:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   42 |   for(register int i = 1; i <= n; ++i){
      |                    ^
Main.cpp:120:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  120 |   for(register int i = 1; i <= n; ++i){
      |                    ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 4700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4444 KB Output is correct
2 Correct 19 ms 4888 KB Output is correct
3 Correct 18 ms 4956 KB Output is correct
4 Correct 22 ms 5440 KB Output is correct
5 Correct 19 ms 5720 KB Output is correct
6 Correct 15 ms 8280 KB Output is correct
7 Correct 16 ms 8276 KB Output is correct
8 Correct 19 ms 8540 KB Output is correct
9 Correct 26 ms 8764 KB Output is correct
10 Correct 24 ms 9016 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 4700 KB Output isn't correct
2 Halted 0 ms 0 KB -