oj.uz

Submission #952463

# Submission time Handle Problem Language Result Execution time Memory
952463 2024-03-24T02:48:59 Z NK_ Superpozicija (COCI22_superpozicija) C++17
30 / 110
 18 ms 3260 KB 
// 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, -1); int open = N / 2; vi ans(N, -1), take(2 * N, 0); 
	for(int i = 0; i < N; i++) {
		int x = A[i][0], y = A[i][1];
		if (S[x] == S[y]) {
			if (S[x] == '(') { ans[i] = 0; open--; take[x] = 1; } // take first
			else { ans[i] = 1; take[y] = 1; } // take last
		} else I[x] = I[y] = i;
	}

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

		assert(A[x] == (array<int, 2>{i, j}));

		if (S[i] == '(') {
		 	if (open > 0) { open--; ans[x] = 0; take[i] = 1; } 
		 	else { ans[x] = 1; take[j] = 1; }
		} else {
			if (open > 0) { open--; ans[x] = 1; take[j] = 1; } 
		 	else { ans[x] = 0; take[i] = 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.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 604 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 12 ms 344 KB Output is correct
2 Correct 13 ms 748 KB Output is correct
3 Correct 12 ms 1116 KB Output is correct
4 Correct 13 ms 1368 KB Output is correct
5 Correct 11 ms 1628 KB Output is correct
6 Correct 7 ms 1884 KB Output is correct
7 Correct 9 ms 2140 KB Output is correct
8 Correct 11 ms 2536 KB Output is correct
9 Correct 13 ms 2904 KB Output is correct
10 Correct 14 ms 3048 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 14 ms 344 KB Output is correct
3 Correct 15 ms 832 KB Output is correct
4 Correct 13 ms 1148 KB Output is correct
5 Correct 18 ms 1504 KB Output is correct
6 Correct 16 ms 1796 KB Output is correct
7 Correct 7 ms 1880 KB Output is correct
8 Correct 12 ms 2396 KB Output is correct
9 Correct 11 ms 2560 KB Output is correct
10 Correct 16 ms 3048 KB Output is correct
11 Correct 18 ms 3260 KB Output is correct

Subtask #4
0 / 70.0

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