Submission #545929

#	Time	Username	Problem	Language	Result	Execution time	Memory
545929		rainboy	Building Skyscrapers (CEOI19_skyscrapers)	C11	100 / 100	338 ms	35516 KiB

skyscrapers

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

#define N	150000

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

unsigned int X = 12345;

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

int dx[] = { 0, 1, 0, -1, -1, 1, 1, -1 };
int dy[] = { 1, 0, -1, 0, 1, 1, -1, -1 };

int xx[N], yy[N];

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

		while (j < k)
			if (ii[j] == i_)
				j++;
			else if (xx[ii[j]] < xx[i_] || xx[ii[j]] == xx[i_] && yy[ii[j]] < yy[i_]) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		sort(ii, l, i);
		l = k;
	}
}

int ds[N * 8];

int find(int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}

void join(int i, int j) {
	i = find(i);
	j = find(j);
	if (i == j)
		return;
	if (ds[i] > ds[j])
		ds[i] = j;
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i;
	}
}

int jj[N][8], ta[N], tb[N];

void dfs(int f, int i) {
	static int time;
	int h;

	ta[i] = tb[i] = ++time;
	for (h = 0; h < 8; h++) {
		int j = jj[i][h];

		if (j == -1)
			continue;
		if (!ta[j]) {
			dfs(i * 8 + h, j);
			if (tb[j] < ta[i])
				join(i * 8 + h, f);
			tb[i] = min(tb[i], tb[j]);
		} else if (ta[j] < ta[i]) {
			join(i * 8 + h, f);
			tb[i] = min(tb[i], ta[j]);
		}
	}
}

int next[N * 4], prev[N * 4], kk[N];

int ok(int i) {
	int h, r, j, k;

	r = -1;
	for (h = 0; h < 8; h++)
		if (jj[i / 4][h] != -1) {
			if (r == -1)
				r = find(i / 4 * 8 + h);
			else if (find(i / 4 * 8 + h) != r)
				return 0;
		}
	k = 1;
	for (j = next[i]; j != i && j / 4 == i / 4; j = next[j])
		k++;
	if (j == i)
		return 1;
	for (j = prev[i]; j / 4 == i / 4; j = prev[j])
		k++;
	return kk[i / 4] == k;
}

int pq[N], iq[1 + N], cnt;

int lt(int i, int j) { return i > 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) {
	if (!pq[i])
		pq[i] = ++cnt, pq_up(i);
}

void pq_remove(int i) {
	if (pq[i]) {
		int j = iq[cnt--];

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

int pq_first() { return iq[1]; }

int main() {
	static int ii[N], hh[N], ii_[N * 4], ans[N];
	int n, n_, t, h, i, j, k;

	scanf("%d%d", &n, &t);
	for (i = 0; i < n; i++) {
		scanf("%d%d", &xx[i], &yy[i]);
		ii[i] = i;
	}
	sort(ii, 0, n);
	memset(ds, -1, n * 8 * sizeof *ds);
	for (h = 0; h < 8; h++)
		for (i = 0, j = 0; i < n; i++) {
			int x = xx[ii[i]] + dx[h], y = yy[ii[i]] + dy[h];

			while (j < n && (xx[ii[j]] < x || xx[ii[j]] == x && yy[ii[j]] < y))
				j++;
			if (j < n && xx[ii[j]] == x && yy[ii[j]] == y) {
				join(ii[i] * 8 + h, ii[j] * 8 + h ^ 2);
				jj[ii[i]][h] = ii[j];
			} else
				jj[ii[i]][h] = -1;
		}
	dfs(-1, 0);
	for (i = 0; i < n; i++)
		if (!ta[i]) {
			printf("NO\n");
			return 0;
		}
	i = ii[0], h = 0, k = 0;
	do {
		hh[i] = h, kk[i]++, ii_[k++] = i * 4 + h;
		if (jj[i][h + 4] != -1)
			i = jj[i][h + 4], h = (h + 3) % 4;
		else if (jj[i][h] != -1)
			i = jj[i][h];
		else
			h = (h + 1) % 4;
	} while (i != ii[0] || h != 0);
	for (h = 0; h < k; h++)
		next[ii_[h]] = ii_[(h + 1) % k], prev[ii_[(h + 1) % k]] = ii_[h];
	for (h = 0; h < k; h++)
		if (ok(ii_[h]))
			pq_add(ii_[h] / 4);
		else
			pq_remove(ii_[h] / 4);
	n_ = 0;
	while (cnt) {
		int i_, j_;

		i = pq_first(), pq_remove(i);
		ans[n_++] = i;
		if (n_ == n)
			break;
		for (h = 0; h < 8; h++)
			if (jj[i][h] != -1)
				jj[jj[i][h]][h ^ 2] = -1, jj[i][h] = -1;
		i_ = i * 4 + hh[i];
		while (i_ / 4 == i)
			i_ = prev[i_];
		j_ = i * 4 + hh[i];
		while (j_ / 4 == i)
			j_ = next[j_];
		kk[i_ / 4]--, kk[j_ / 4]--;
		i = i_ / 4, h = i_ % 4, k = 0;
		do {
			hh[i] = h, kk[i]++, ii_[k++] = i * 4 + h;
			if (jj[i][h + 4] != -1)
				i = jj[i][h + 4], h = (h + 3) % 4;
			else if (jj[i][h] != -1)
				i = jj[i][h];
			else
				h = (h + 1) % 4;
		} while (i != j_ / 4 || h != j_ % 4);
		hh[i] = h, kk[i]++, ii_[k++] = i * 4 + h;
		for (h = 0; h + 1 < k; h++)
			next[ii_[h]] = ii_[h + 1], prev[ii_[h + 1]] = ii_[h];
		for (h = 0; h < k; h++)
			if (ok(ii_[h]))
				pq_add(ii_[h] / 4);
			else 
				pq_remove(ii_[h] / 4);
	}
	printf("YES\n");
	while (n_--)
		printf("%d\n", ans[n_] + 1);
	return 0;
}

Compilation message (stderr)

skyscrapers.c: In function 'sort':
skyscrapers.c:26:55: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   26 |    else if (xx[ii[j]] < xx[i_] || xx[ii[j]] == xx[i_] && yy[ii[j]] < yy[i_]) {
      |                                   ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
skyscrapers.c: In function 'main':
skyscrapers.c:161:53: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  161 |    while (j < n && (xx[ii[j]] < x || xx[ii[j]] == x && yy[ii[j]] < y))
      |                                      ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
skyscrapers.c:164:35: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  164 |     join(ii[i] * 8 + h, ii[j] * 8 + h ^ 2);
      |                         ~~~~~~~~~~^~~
skyscrapers.c:150:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |  scanf("%d%d", &n, &t);
      |  ^~~~~~~~~~~~~~~~~~~~~
skyscrapers.c:152:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 12 / 12
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20
• Subtask 6: 10 / 10
• Subtask 7: 19 / 19