Submission #493305

#	Time	Username	Problem	Language	Result	Execution time	Memory
493305		rainboy	Izvanzemaljci (COI21_izvanzemaljci)	C11	26 / 100	57 ms	5336 KiB

izvanzemaljci

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

#define N	100000
#define INF	0x3f3f3f3f3f3f3f3fLL

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;
}

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

void solve1(long long *xx_, long long *yy_, long long *ll_) {
	int i;
	long long xmn, xmx, ymn, ymx, l;

	xmn = INF, xmx = -INF, ymn = INF, ymx = -INF;
	for (i = 0; i < n; i++) {
		xmn = min(xmn, xx[i]), xmx = max(xmx, xx[i]);
		ymn = min(ymn, yy[i]), ymx = max(ymx, yy[i]);
	}
	l = max(max(xmx - xmn, ymx - ymn), 1);
	if (ll_[0] > l)
		xx_[0] = xmn, yy_[0] = ymn, ll_[0] = l;
}

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 solve2(int *ii, int n, long long *xx_, long long *yy_, long long *ll_) {
	static long long yld[N], ylu[N], yrd[N], yru[N];
	int i;
	long long x1_, y1_, l1_, x2_, y2_, l2_;

	for (i = 0; i < n; i++) {
		yld[i] = min(i == 0 ? INF : yld[i - 1], yy[ii[i]]);
		ylu[i] = max(i == 0 ? -INF : ylu[i - 1], yy[ii[i]]);
	}
	for (i = n - 1; i >= 0; i--) {
		yrd[i] = min(i + 1 == n ? INF : yrd[i + 1], yy[ii[i]]);
		yru[i] = max(i + 1 == n ? -INF : yru[i + 1], yy[ii[i]]);
	}
	x1_ = y1_ = x2_ = y2_ = -1, l1_ = l2_ = INF;
	for (i = 0; i + 1 < n; i++)
		if (xx[ii[i]] != xx[ii[i + 1]]) {
			long long x1, y1, l1, x2, y2, l2;

			l1 = max(max(xx[ii[i]] - xx[ii[0]], ylu[i] - yld[i]), 1);
			x1 = xx[ii[i]] - l1, y1 = ylu[i] - l1;
			l2 = max(max(xx[ii[n - 1]] - xx[ii[i + 1]], yru[i + 1] - yrd[i + 1]), 1);
			x2 = xx[ii[i + 1]], y2 = yru[i + 1] - l2;
			if (max(l1_, l2_) > max(l1, l2))
				x1_ = x1, y1_ = y1, l1_ = l1, x2_ = x2, y2_ = y2, l2_ = l2;
		}
	if (max(ll_[0], ll_[1]) > max(l1_, l2_))
		xx_[0] = x1_, yy_[0] = y1_, ll_[0] = l1_, xx_[1] = x2_, yy_[1] = y2_, ll_[1] = l2_;
}

void solve3() {
	xx[0] = yy[0] = n;
}

int main() {
	static int ii[N];
	static long long xx_[3], yy_[3], ll_[3];
	int k, h, i, u;

	scanf("%d%d", &n, &k);
	for (i = 0; i < n; i++)
		scanf("%lld%lld", &xx[i], &yy[i]);
	if (n == 1) {
		printf("%lld %lld 1\n", xx[0], yy[0]);
		if (k == 2)
			printf("%lld %lld 1\n", xx[0] - 2, yy[0] - 2);
		return 0;
	}
	ll_[0] = INF;
	if (k == 1)
		solve1(xx_, yy_, ll_);
	else if (k == 2)
		for (u = 0; u < 2; u++) {
			long long tmp;

			for (i = 0; i < n; i++)
				ii[i] = i;
			sort(ii, 0, n);
			solve2(ii, n, xx_, yy_, ll_);
			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], ll_[h]);
	return 0;
}

Compilation message (stderr)

izvanzemaljci.c: In function 'main':
izvanzemaljci.c:89:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |  scanf("%d%d", &n, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~
izvanzemaljci.c:91:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |   scanf("%lld%lld", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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