Submission #378041

#	Time	Username	Problem	Language	Result	Execution time	Memory
378041		rainboy	Jakarta Skyscrapers (APIO15_skyscraper)	C11	100 / 100	105 ms	3052 KiB

skyscraper

/* https://oj.uz/submission/216252 (Benq) */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	30000
#define M	30000
#define M_	(M * 2 + 1)

int min(int a, int b) { return a < b ? a : b; }

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int *eh[N], eo[N];

void append(int i, int h) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		eh[i] = (int *) realloc(eh[i], o * 2 * sizeof *eh[i]);
	eh[i][o] = h;
}

int ii[M], jj[M], rr[M];

int compare(int h1, int h2) {
	return jj[h1] != jj[h2] ? jj[h1] - jj[h2] : (rr[h1] != rr[h2] ? rr[h1] - rr[h2] : ii[h1] - ii[h2]);
}

void sort(int *hh, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;

		while (j < k) {
			int c = compare(hh[j], h);

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
			}
		}
		sort(hh, l, i);
		l = k;
	}
}

int main() {
	static int hh[M], kl[M], kr[M], qu[M_], dd[M_];
	int n, m, h, i, j, s, t, o, head, tail;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		eh[i] = (int *) malloc(2 * sizeof *eh[i]);
	for (h = 0; h < m; h++) {
		scanf("%d%d", &i, &j);
		ii[h] = i, jj[h] = j, rr[h] = i % j;
		append(i, h);
	}
	for (h = 0; h < m; h++)
		hh[h] = h;
	sort(hh, 0, m);
	for (h = 0; h < m; h++) {
		int h_, p, q, r;

		h_ = hh[h], p = h == 0 ? -1 : hh[h - 1], q = h + 1 == m ? -1 : hh[h + 1];
		i = ii[h_], j = jj[h_], r = rr[h_];
		kl[h_] = h == 0 || jj[p] != j || rr[p] != r ? i / j : (i - ii[p]) / j;
		kr[h_] = h + 1 == m || jj[q] != j || rr[q] != r ? (n - 1 - i) / j : (ii[q] - i) / j;
	}
	s = ii[0], t = ii[1];
	if (s == t) {
		printf("0\n");
		return 0;
	}
	head = tail = 0;
	i = s;
	for (o = eo[i]; o--; ) {
		h = eh[i][o];
		if (kl[h] > 0)
			qu[tail] = h * N + kl[h] - 1, tail = tail + 1 == M_ ? 0 : tail + 1;
		if (kr[h] > 0)
			qu[tail] = h * N + kl[h] + 1, tail = tail + 1 == M_ ? 0 : tail + 1;
	}
	eo[i] = 0;
	while (head != tail) {
		int hk, k, d;

		hk = qu[head], d = dd[head] + 1, head = head + 1 == M_ ? 0 : head + 1;
		h = hk / N, k = hk % N - kl[h], i = ii[h] + k * jj[h];
		if (i == t) {
			printf("%d\n", d);
			return 0;
		}
		if (k < 0 && k > -kl[h])
			dd[tail] = d, qu[tail] = h * N + kl[h] + k - 1, tail = tail + 1 == M_ ? 0 : tail + 1;
		else if (k > 0 && k < kr[h])
			dd[tail] = d, qu[tail] = h * N + kl[h] + k + 1, tail = tail + 1 == M_ ? 0 : tail + 1;
		if (eo[i]) {
			for (o = eo[i]; o--; ) {
				h = eh[i][o];
				if (kl[h] > 0)
					dd[tail] = d, qu[tail] = h * N + kl[h] - 1, tail = tail + 1 == M_ ? 0 : tail + 1;
				if (kr[h] > 0)
					dd[tail] = d, qu[tail] = h * N + kl[h] + 1, tail = tail + 1 == M_ ? 0 : tail + 1;
			}
			eo[i] = 0;
		}
	}
	printf("-1\n");
	return 0;
}

Compilation message (stderr)

skyscraper.c: In function 'append':
skyscraper.c:23:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   23 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
skyscraper.c: In function 'main':
skyscraper.c:60:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   60 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
skyscraper.c:64:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   64 |   scanf("%d%d", &i, &j);
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 43 / 43