Submission #587276

#	Time	Username	Problem	Language	Result	Execution time	Memory
587276		rainboy	Superpozicija (COCI22_superpozicija)	C11	110 / 110	36 ms	4732 KiB

Main

#include <stdio.h>
#include <string.h>

#define N	100000

int hh[N * 2], rr[N * 2], iq[1 + N], pq[N * 2], cnt;

int lt(int i, int j) { return rr[i] < rr[j]; }

int p2(int p) {
	return (p *= 2) > cnt ? 0 : (p < cnt && lt(iq[p + 1], iq[p]) ? p + 1 : p);
}

void pq_up(int i) {
	int p, q, j;

	for (p = pq[i]; (q = p / 2) && lt(i, j = iq[q]); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_dn(int i) {
	int p, q, j;

	for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_add(int i) {
	pq[i] = ++cnt, pq_up(i);
}

int pq_remove_first() {
	int i = iq[1], j = iq[cnt--];

	if (j != i)
		pq[j] = 1, pq_dn(j);
	pq[i] = 0;
	return i;
}

int main() {
	int t;

	scanf("%d", &t);
	while (t--) {
		static char cc[N * 2 + 1], tt[N];
		static int dd[N * 2];
		int n, h, i, l, r, d;

		scanf("%d%s", &n, cc);
		memset(dd, 0, n * 2 * sizeof *dd);
		memset(hh, -1, n * 2 * sizeof *hh), memset(rr, -1, n * 2 * sizeof *rr);
		for (h = 0; h < n; h++) {
			int l, r;

			scanf("%d%d", &l, &r), l--, r--;
			if (cc[l] == '(' && cc[r] == '(')
				tt[h] = 0, dd[l]++;
			else if (cc[l] == ')' && cc[r] == ')')
				tt[h] = 1, dd[r]--;
			else {
				hh[l] = h, rr[l] = r;
				if (cc[l] == '(')
					tt[h] = 1, dd[r]--;
				else
					tt[h] = 0, dd[l]--;
			}
		}
		memset(pq, 0, n * 2 * sizeof *pq), cnt = 0;
		for (i = 0, d = 0; i < n * 2; i++) {
			if (rr[i] != -1)
				pq_add(i);
			d += dd[i];
			if (d < 0) {
				if (cnt == 0) {
					d = -1;
					break;
				}
				l = pq_remove_first(), h = hh[l], r = rr[l];
				tt[h] ^= 1;
				if (r <= i)
					d += 2;
				else
					d++, dd[r]++;
			}
		}
		if (d != 0)
			printf("-1\n");
		else {
			for (h = 0; h < n; h++)
				printf("%d ", tt[h]);
			printf("\n");
		}
	}
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:46:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |  scanf("%d", &t);
      |  ^~~~~~~~~~~~~~~
Main.c:52:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |   scanf("%d%s", &n, cc);
      |   ^~~~~~~~~~~~~~~~~~~~~
Main.c:58:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |    scanf("%d%d", &l, &r), l--, r--;
      |    ^~~~~~~~~~~~~~~~~~~~~

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