Submission #493485

#	Time	Username	Problem	Language	Result	Execution time	Memory
493485		rainboy	Izvanzemaljci (COI21_izvanzemaljci)	C11	26 / 100	65 ms	5060 KiB

izvanzemaljci

#include <stdio.h>
#include <sys/time.h>

#define N	100000
#define LINF	0x3f3f3f3f3f3f3f3fLL
#define X	1000000001

long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }

unsigned int Z = 12345;

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

int xx[N], yy[N], 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 (xx[ii[j]] == xx[i_])
				j++;
			else if (xx[ii[j]] < xx[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;
	}
}

void solve1(int *ii, int n, long long *xx_, long long *yy_, long long *ss_) {
	int i, i_, x, y, xl, xr, yl, yr, s;

	if (n == 0) {
		if (ss_[0] > 1)
			xx_[0] = X + 1, yy_[0] = X + 1, ss_[0] = 1;
		return;
	}
	xl = X, xr = -X, yl = X, yr = -X;
	for (i = 0; i < n; i++) {
		i_ = ii[i], x = xx[i_], y = yy[i_];
		xl = min(xl, x), xr = max(xr, x);
		yl = min(yl, y), yr = max(yr, y);
	}
	s = max(max(xr - xl, yr - yl), 1);
	if (ss_[0] > s)
		xx_[0] = xl, yy_[0] = yl, ss_[0] = s;
}

void solve2(int *ii, int n, long long *xx_, long long *yy_, long long *ss_) {
	static int ypl[N], ypr[N], yql[N], yqr[N];
	int i, xl, xr, y, yl, yr;

	if (n == 0) {
		if (max(ss_[0], ss_[1]) > 1) {
			xx_[0] = -(X + 2), yy_[0] = -(X + 2), ss_[0] = 1;
			xx_[1] = X + 1, yy_[1] = -(X + 2), ss_[1] = 1;
		}
		return;
	}
	xl = xx[ii[0]], xr = xx[ii[n - 1]];
	yl = X, yr = -X;
	for (i = 0; i < n; i++) {
		y = yy[ii[i]];
		ypl[i] = yl = min(yl, y);
		ypr[i] = yr = max(yr, y);
	}
	yl = X, yr = -X;
	for (i = n - 1; i >= 0; i--) {
		y = yy[ii[i]];
		yql[i] = yl = min(yl, y);
		yqr[i] = yr = max(yr, y);
	}
	for (i = -1; i < n; i++) {
		long long xp, xq, x0, y0, s0, x1, y1, s1;

		xp = i == -1 ? -(X + 1) : xx[ii[i]], xq = i + 1 == n ? X + 1 : xx[ii[i + 1]];
		if (xp == xq)
			continue;
		if (i == -1)
			s0 = 1, x0 = -(X + 2), y0 = -(X + 2);
		else
			s0 = max(max(xp - xl, ypr[i] - ypl[i]), 1), x0 = xp - s0, y0 = ypr[i] - s0;
		if (i + 1 == n)
			s1 = 1, x1 = X + 1, y1 = -(X + 2);
		else
			s1 = max(max(xr - xq, yqr[i + 1] - yql[i + 1]), 1), x1 = xq, y1 = yqr[i + 1] - s1;
		if (max(ss_[0], ss_[1]) > max(s0, s1))
			xx_[0] = x0, yy_[0] = y0, ss_[0] = s0, xx_[1] = x1, yy_[1] = y1, ss_[1] = s1;
	}
}

void solve21(int *ii, int n, long long *xx_, long long *yy_, long long *ss_) {
	static long long xx1[3], yy1[3], ll1[3];
	static int ii1[N], ii2[N];
	long long lower, upper;
	int n1, n2, h, i;

	lower = -X, upper = X;
	while (upper - lower > 1) {
		long long y = (lower + upper) / 2;

		n1 = n2 = 0;
		for (i = 0; i < n; i++)
			if (yy[ii[i]] <= y)
				ii1[n1++] = ii[i];
			else
				ii2[n2++] = ii[i];
		ll1[0] = ll1[1] = ll1[2] = LINF;
		solve2(ii1, n1, xx1, yy1, ll1);
		solve1(ii2, n2, xx1 + 2, yy1 + 2, ll1 + 2);
		if (max(max(ss_[0], ss_[1]), ss_[2]) > max(max(ll1[0], ll1[1]), ll1[2]))
			for (h = 0; h < 3; h++)
				xx_[h] = xx1[h], yy_[h] = yy1[h], ss_[h] = ll1[h];
		if (ll1[0] == LINF || ll1[1] == LINF || ll1[2] != LINF && max(ll1[0], ll1[1]) < ll1[2])
			lower = y;
		else
			upper = y;
	}
}

void solve111(int *ii, int n, long long *xx_, long long *yy_, long long *ss_) {
	static long long yld[N], ylu[N], yrd[N], yru[N];
	int i, j;

	for (i = 0; i < n; i++) {
		yld[i] = min(i == 0 ? LINF : yld[i - 1], yy[ii[i]]);
		ylu[i] = max(i == 0 ? -LINF : ylu[i - 1], yy[ii[i]]);
	}
	for (i = n - 1; i >= 0; i--) {
		yrd[i] = min(i + 1 == n ? LINF : yrd[i + 1], yy[ii[i]]);
		yru[i] = max(i + 1 == n ? -LINF : yru[i + 1], yy[ii[i]]);
	}
	for (i = 1; i < n; i++) {
		long long yd, yu;

		yd = LINF, yu = -LINF;
		for (j = i; j + 1 < n; j++) {
			yd = min(yd, yy[ii[j]]), yu = max(yu, yy[ii[j]]);
			if (xx[ii[i - 1]] < xx[ii[i]] && xx[ii[j]] < xx[ii[j + 1]] && max(yu - yd, 1) <= xx[ii[j + 1]] - xx[ii[i - 1]] - 2) {
				long long x1, y1, l1, x2, y2, l2, x3, y3, l3;

				l1 = max(max(xx[ii[i - 1]] - xx[ii[0]], ylu[i - 1] - yld[i - 1]), 1);
				x1 = xx[ii[i - 1]] - l1, y1 = ylu[i - 1] - l1;
				l2 = max(max(xx[ii[n - 1]] - xx[ii[j + 1]], yru[j + 1] - yrd[j + 1]), 1);
				x2 = xx[ii[j + 1]], y2 = yru[j + 1] - l2;
				l3 = max(xx[ii[j]] - xx[ii[i]], max(yu - yd, 1));
				x3 = min(xx[ii[i]], xx[ii[j + 1]] - 1 - l3), y3 = yu - l3;
				if (max(max(ss_[0], ss_[1]), ss_[2]) > max(max(l1, l2), l3))
					xx_[0] = x1, yy_[0] = y1, ss_[0] = l1, xx_[1] = x2, yy_[1] = y2, ss_[1] = l2, xx_[2] = x3, yy_[2] = y3, ss_[2] = l3;
			}
		}
	}
}

int main() {
	static int ii[N];
	static long long xx_[3], yy_[3], ss_[3];
	int k, h, i, r;
	long long tmp;

	scanf("%d%d", &n, &k);
	for (i = 0; i < n; i++) {
		scanf("%d%d", &xx[i], &yy[i]);
		ii[i] = i;
	}
	ss_[0] = LINF;
	if (k == 1)
		solve1(ii, n, xx_, yy_, ss_);
	else if (k == 2)
		for (r = 0; r < 2; r++) {
			sort(ii, 0, n);
			solve2(ii, n, xx_, yy_, ss_);
			for (i = 0; i < n; i++)
				tmp = xx[i], xx[i] = yy[i], yy[i] = tmp;
			for (h = 0; h < k; h++)
				tmp = xx_[h], xx_[h] = yy_[h], yy_[h] = tmp;
		}
	else if (k == 3) {
		return 0;
		for (r = 0; r < 4; r++) {
			for (i = 0; i < n; i++)
				ii[i] = i;
			sort(ii, 0, n);
			solve21(ii, n, xx_, yy_, ss_);
			for (i = 0; i < n; i++)
				tmp = xx[i], xx[i] = -yy[i], yy[i] = tmp;
			for (h = 0; h < k; h++)
				tmp = xx_[h], xx_[h] = -yy_[h], yy_[h] = tmp, xx_[h] -= ss_[h];
		}
		for (r = 0; r < 2; r++) {
			for (i = 0; i < n; i++)
				ii[i] = i;
			sort(ii, 0, n);
			solve111(ii, n, xx_, yy_, ss_);
			for (i = 0; i < n; i++)
				tmp = xx[i], xx[i] = yy[i], yy[i] = tmp;
			for (h = 0; h < k; h++)
				tmp = xx_[h], xx_[h] = yy_[h], yy_[h] = tmp;
		}
	}
	for (h = 0; h < k; h++)
		printf("%lld %lld %lld\n", xx_[h], yy_[h], ss_[h]);
	return 0;
}

Compilation message (stderr)

izvanzemaljci.c: In function 'solve21':
izvanzemaljci.c:122:58: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  122 |   if (ll1[0] == LINF || ll1[1] == LINF || ll1[2] != LINF && max(ll1[0], ll1[1]) < ll1[2])
      |                                           ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
izvanzemaljci.c: In function 'main':
izvanzemaljci.c:169:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |  scanf("%d%d", &n, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~
izvanzemaljci.c:171:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  171 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 21 / 21
• Subtask 3: 0 / 12
• Subtask 4: 0 / 30
• Subtask 5: 0 / 32