Submission #952671

#	Time	Username	Problem	Language	Result	Execution time	Memory
952671		NK_	Superpozicija (COCI22_superpozicija)	C++17	110 / 110	62 ms	6620 KiB

Main

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())

template<class T> using V = vector<T>;
using vi = V<int>;

void solve() {
	int N; cin >> N;
	string S; cin >> S;

	vi L(N), R(N), ans(N); 
	V<array<int, 2>> A; set<array<int, 2>> F; vi rem; set<int> pos; 
	for(int i = 0; i < N; i++) {
		cin >> L[i] >> R[i]; --L[i], --R[i];

		if (S[L[i]] == '(' && S[R[i]] == '(') {
			rem.pb(L[i]); ans[i] = 0;
		}

		if (S[L[i]] == ')' && S[R[i]] == ')') {
			pos.insert(R[i]); ans[i] = 1;
		}

		if (S[L[i]] == '(' && S[R[i]] == ')') {
			pos.insert(R[i]);
			A.pb({L[i], i});
			ans[i] = 1;
		}

		if (S[L[i]] == ')' && S[R[i]] == '(') {
			pos.insert(L[i]);
			A.pb({L[i], i});
			ans[i] = 0;
		}
	}

	auto pair = [&](int x) {
		auto it = pos.lower_bound(x);
		if (it == end(pos)) return 0;
		pos.erase(it); return 1;
	};

	for(auto& x : rem) {
		if (!pair(x)) {
			cout << -1 << nl;
			return;
		}
	}

	sort(begin(A), end(A));

	int p = -1;
	while(sz(pos)) {
		int lim = *begin(pos);

		while(p + 1 < sz(A) && A[p + 1][0] <= lim) {
			++p; int x = A[p][1];
			F.insert({R[x], x});
		}

		bool ok = 1;
		if (!sz(F)) ok = 0;
		else {
			int x = (*begin(F))[1]; F.erase(begin(F));
			ans[x] ^= 1;
			if (!pair(L[x])) ok = 0;
			if (!pair(R[x])) ok = 0;
		}	

		if (!ok) {
			cout << -1 << nl;
			return;
		}
	}

	// cout << 1 << nl;
	for(auto& x : ans) cout << x << " ";
	cout << nl;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int T; cin >> T; while(T--) {
		solve();
	}

	exit(0-0);
}

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