Submission #544615

#	Time	Username	Problem	Language	Result	Execution time	Memory
544615		rainboy	Demarcation (BOI14_demarcation)	C11	100 / 100	145 ms	8460 KiB

demarcation

/* upsolve after reading analysis */
#include <stdio.h>

#define N	100000
#define M	(N * 2)

unsigned int X = 12345;

int abs(int a) { return a > 0 ? a : -a; }

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

void flip(int *xx, int *yy, int n) {
	int i, j, tmp;

	for (i = 0, j = n - 1; i < j; i++, j--) {
		tmp = xx[i], xx[i] = xx[j], xx[j] = tmp;
		tmp = yy[i], yy[i] = yy[j], yy[j] = tmp;
	}
	for (i = 0; i < n; i++)
		xx[i] = -xx[i];
}

void rotate(int *xx, int *yy, int n) {
	int i, tmp;

	for (i = 0; i < n; i++)
		tmp = xx[i], xx[i] = -yy[i], yy[i] = tmp;
}

int check1(int *xx1, int *yy1, int *xx2, int *yy2, int n) {
	int i_, j_, i, j, x, y;

	i_ = -1;
	for (i = 0; i < n; i++)
		if (i_ == -1 || xx1[i_] > xx1[i] || xx1[i_] == xx1[i] && yy1[i_] > yy1[i])
			i_ = i;
	j_ = -1;
	for (j = 0; j < n; j++)
		if (j_ == -1 || xx2[j_] > xx2[j] || xx2[j_] == xx2[j] && yy2[j_] > yy2[j])
			j_ = j;
	x = xx1[i_] - xx2[j_], y = yy1[i_] - yy2[j_];
	for (i = 0; i < n; i++)
		if (xx1[(i + i_) % n] - xx2[(i + j_) % n] != x || yy1[(i + i_) % n] - yy2[(i + j_) % n] != y)
			return 0;
	return 1;
}

int check_(int *xx1, int *yy1, int *xx2, int *yy2, int n) {
	int a, b;

	for (a = 0; a < 2; a++) {
		for (b = 0; b < 4; b++) {
			if (check1(xx1, yy1, xx2, yy2, n))
				return 1;
			rotate(xx2, yy2, n);
		}
		flip(xx2, yy2, n);
	}
	return 0;
}

int xx[N], yy[N], n;

int check(int i_, int j_, int x) {
	static int xx1[N], yy1[N], xx2[N], yy2[N];
	int n1, n2, i;

	n1 = 0;
	i = (i_ + 1) % n;
	while (1) {
		if (i == (i_ + 1) % n) {
			if (xx[i] != x) {
				xx1[n1] = x, yy1[n1] = yy[i], n1++;
				xx1[n1] = xx[i], yy1[n1] = yy[i], n1++;
			}
		} else if (i == j_) {
			if (xx[i] != x) {
				xx1[n1] = xx[i], yy1[n1] = yy[i], n1++;
				xx1[n1] = x, yy1[n1] = yy[i], n1++;
			}
			break;
		} else
			xx1[n1] = xx[i], yy1[n1] = yy[i], n1++;
		i = (i + 1) % n;
	}
	n2 = 0;
	i = (j_ + 1) % n;
	while (1) {
		if (i == (j_ + 1) % n) {
			if (xx[i] != x) {
				xx2[n2] = x, yy2[n2] = yy[i], n2++;
				xx2[n2] = xx[i], yy2[n2] = yy[i], n2++;
			}
		} else if (i == i_) {
			if (xx[i] != x) {
				xx2[n2] = xx[i], yy2[n2] = yy[i], n2++;
				xx2[n2] = x, yy2[n2] = yy[i], n2++;
			}
			break;
		} else
			xx2[n2] = xx[i], yy2[n2] = yy[i], n2++;
		i = (i + 1) % n;
	}
	return n1 == n2 && check_(xx1, yy1, xx2, yy2, n1);
}

int xx_[M], kk1[M], kk2[M], tt[M], m;
int iq[1 + M], pq[M], cnt;

int lt(int i, int j) {
	return xx_[i] != xx_[j] ? xx_[i] < xx_[j] : tt[i] > tt[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 x, int k1, int k2, int t) {
	int i = m++;

	xx_[i] = x, kk1[i] = k1, kk2[i] = k2, tt[i] = t;
	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 zz[1 + N], ll[1 + N], rr[1 + N], kk[1 + N], _, u_, l_, r_;

int node(int k) {
	zz[_] = rand_();
	ll[_] = rr[_] = 0;
	kk[_] = k;
	return _++;
}

void split(int u, int k) {
	int c;

	if (u == 0) {
		u_ = l_ = r_ = 0;
		return;
	}
	c = yy[k] - yy[kk[u]];
	if (c < 0) {
		split(rr[u], k);
		rr[u] = l_, l_ = u;
	} else if (c > 0) {
		split(ll[u], k);
		ll[u] = r_, r_ = u;
	} else {
		u_ = u, l_ = ll[u], r_ = rr[u];
		ll[u] = rr[u] = 0;
	}
}

int merge(int u, int v) {
	if (u == 0)
		return v;
	if (v == 0)
		return u;
	if (zz[u] < zz[v]) {
		rr[u] = merge(rr[u], v);
		return u;
	} else {
		ll[v] = merge(u, ll[v]);
		return v;
	}
}

void tr_add(int k) {
	split(u_, k);
	u_ = merge(merge(l_, node(k)), r_);
}

void tr_remove(int k) {
	split(u_, k);
	u_ = merge(l_, r_);
}

int tr_lower(int k) {
	int u = u_, k_ = -1;

	while (u)
		if (yy[kk[u]] > yy[k])
			k_ = kk[u], u = rr[u];
		else
			u = ll[u];
	return k_;
}

int tr_higher(int k) {
	int u = u_, k_ = -1;

	while (u)
		if (yy[kk[u]] < yy[k])
			k_ = kk[u], u = ll[u];
		else
			u = rr[u];
	return k_;
}

long long pp[N * 2];

void add(int i, int j, int x_) {
	if (xx[i] < xx[(i + 1) % n] && xx[j] > xx[(j + 1) % n]) {
		long long p, x;
		int x1, x2, x3, x4;

		p = j < i - 1 ? pp[i - 1] - pp[j] : pp[i - 1 + n] - pp[j];
		x1 = xx[i], x2 = xx[(j + 1) % n];
		if ((x = pp[n - 1] / 2 - p + x1 + x2) % 2 == 0) {
			x /= 2;
			x3 = xx[(i + 1) % n], x4 = xx[j];
			if (x >= x_ && x <= x3 && x <= x4)
				pq_add(x, i, j, 0);
		}
		x_ = 0;
	}
}

int main() {
	int i, i_, j, r, tmp;

	scanf("%d", &n);
	i_ = -1;
	for (i = 0; i < n; i++) {
		scanf("%d%d", &xx[i], &yy[i]);
		if (i_ == -1 || xx[i_] > xx[i] || xx[i_] == xx[i] && yy[i_] > yy[i])
			i_ = i;
	}
	if (xx[(i_ + 1) % n] != xx[i_])
		for (i = 0, j = n - 1; i < j; i++, j--) {
			tmp = xx[i], xx[i] = xx[j], xx[j] = tmp;
			tmp = yy[i], yy[i] = yy[j], yy[j] = tmp;
		}
	for (i = 0; i < n * 2; i++)
		pp[i] = abs(xx[i % n] - xx[(i + 1) % n]) + abs(yy[i % n] - yy[(i + 1) % n]);
	for (i = 1; i < n * 2; i++)
		pp[i] += pp[i - 1];
	if (pp[n - 1] % 2 != 0) {
		printf("NO\n");
		return 0;
	}
	for (r = 0; r < 2; r++) {
		int i_, j_, x_;

		m = 0, cnt = 0;
		_ = 1, u_ = 0;
		for (i = 0; i < n; i++)
			if (xx[i] != xx[(i + 1) % n]) {
				int x1 = xx[i], x2 = xx[(i + 1) % n];

				if (x1 > x2)
					tmp = x1, x1 = x2, x2 = tmp;
				pq_add(x1, i, i, 1), pq_add(x2, i, i, -1);
			}
		i_ = -1, j_ = -1, x_ = -1;
		while (cnt) {
			int h = pq_remove_first(), l, r;

			if (tt[h] == 1) {
				i = kk1[h], l = tr_lower(i), r = tr_higher(i);
				tr_add(i);
				if (l != -1)
					add(l, i, xx_[h]);
				if (r != -1)
					add(i, r, xx_[h]);
			} else if (tt[h] == -1) {
				i = kk1[h], l = tr_lower(i), r = tr_higher(i);
				tr_remove(i);
				if (l != -1 && r != -1)
					add(l, r, xx_[h] + 1);
			} else
				if (tr_higher(kk1[h]) == kk2[h]) {
					i_ = kk1[h], j_ = kk2[h], x_ = xx_[h];
					break;
				}
		}
		if (i_ != -1 && j_ != -1 && check(i_, j_, x_)) {
			if (r == 0)
				printf("%d %d %d %d\n", x_, yy[i_], x_, yy[j_]);
			else
				printf("%d %d %d %d\n", yy[i_], -x_, yy[j_], -x_);
			return 0;
		}
		rotate(xx, yy, n);
	}
	printf("NO\n");
	return 0;
}

Compilation message (stderr)

demarcation.c: In function 'check1':
demarcation.c:38:57: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   38 |   if (i_ == -1 || xx1[i_] > xx1[i] || xx1[i_] == xx1[i] && yy1[i_] > yy1[i])
      |                                       ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
demarcation.c:42:57: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   42 |   if (j_ == -1 || xx2[j_] > xx2[j] || xx2[j_] == xx2[j] && yy2[j_] > yy2[j])
      |                                       ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
demarcation.c: In function 'main':
demarcation.c:254:53: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  254 |   if (i_ == -1 || xx[i_] > xx[i] || xx[i_] == xx[i] && yy[i_] > yy[i])
      |                                     ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
demarcation.c:250:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  250 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
demarcation.c:253:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  253 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 23 / 23
• Subtask 4: 50 / 50