oj.uz

Submission #587274

# Submission time Handle Problem Language Result Execution time Memory
587274 2022-07-01T14:57:03 Z rainboy Superpozicija (COCI22_superpozicija) C
10 / 110
 28 ms 2768 KB 
#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];
		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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1084 KB Output is correct
2 Correct 23 ms 648 KB Output is correct
3 Correct 28 ms 952 KB Output is correct
4 Correct 24 ms 1068 KB Output is correct
5 Correct 24 ms 1108 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 812 KB Output is correct
2 Correct 16 ms 1516 KB Output is correct
3 Correct 17 ms 1724 KB Output is correct
4 Correct 17 ms 2244 KB Output is correct
5 Correct 16 ms 2644 KB Output is correct
6 Runtime error 1 ms 784 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 21 ms 1108 KB Output is correct
3 Correct 27 ms 1740 KB Output is correct
4 Correct 20 ms 1972 KB Output is correct
5 Correct 27 ms 2528 KB Output is correct
6 Correct 24 ms 2768 KB Output is correct
7 Runtime error 2 ms 728 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #4
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1084 KB Output is correct
2 Correct 23 ms 648 KB Output is correct
3 Correct 28 ms 952 KB Output is correct
4 Correct 24 ms 1068 KB Output is correct
5 Correct 24 ms 1108 KB Output is correct
6 Correct 19 ms 812 KB Output is correct
7 Correct 16 ms 1516 KB Output is correct
8 Correct 17 ms 1724 KB Output is correct
9 Correct 17 ms 2244 KB Output is correct
10 Correct 16 ms 2644 KB Output is correct
11 Runtime error 1 ms 784 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -