Submission #952454

#	Time	Username	Problem	Language	Result	Execution time	Memory
952454		NK_	Superpozicija (COCI22_superpozicija)	C++17	10 / 110	17 ms	4072 KiB

Main

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

using namespace std;

#define nl '\n'
template<class T> using V = vector<T>;

using vi = V<int>;

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

	V<array<int, 2>> A(N); for(auto& x : A) { cin >> x[0] >> x[1]; --x[0], --x[1]; }

	if (N % 2) {
		cout << -1 << nl;
		return;
	}

	vi I(2 * N);
	for(int i = 0; i < N; i++) {
		I[A[i][0]] = 2 * i;
		I[A[i][1]] = 2 * i + 1;
	}

	vi ans(N), take(2 * N); int open = N / 2;
	for(int i = 0; i < 2 * N; i++) if (I[i] != -1) {
		int x = I[i] / 2, j = A[x][1];

		if (S[i] == '(') {
		 	if (open > 0) { open--; ans[x] = 0; take[i] = 1; } 
		 	else { ans[x] = 1; take[j] = 1; }
		} else {
			if (S[i] != S[j]) {
				if (open > 0) { open--; ans[x] = 1; take[j] = 1; }
				else { ans[x] = 0; take[i] = 1; }
			} else { ans[x] = 1; take[j] = 1; }
		}
		
		I[i] = I[j] = -1;
	}

	int bal = 0; for(int i = 0; i < 2 * N; i++) if (take[i]) {
		if (S[i] == '(') bal++;
		else bal--;

		if (bal < 0) {
			cout << -1 << nl;
			return;
		}
	}

	if (bal != 0) {
		cout << -1 << nl;
		return;
	}

	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: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 70