Submission #493312

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
493312	2021-12-10T21:49:16 Z	rainboy	Izvanzemaljci (COI21_izvanzemaljci)	C	56 / 100	219 ms	5340 KB

izvanzemaljci

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

#define N	100000
#define LINF	0x3f3f3f3f3f3f3f3fLL
#define INF	0x3f3f3f3f

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(int *ii, int n, long long *xx_, long long *yy_, long long *ll_) {
	int i;
	long long xmn, xmx, ymn, ymx, l;

	if (n == 0)
		return;
	xmn = LINF, xmx = -LINF, ymn = LINF, ymx = -LINF;
	for (i = 0; i < n; i++) {
		xmn = min(xmn, xx[ii[i]]), xmx = max(xmx, xx[ii[i]]);
		ymn = min(ymn, yy[ii[i]]), ymx = max(ymx, yy[ii[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;

	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 = 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(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(int *ii, int n, long long *xx_, long long *yy_, long long *ll_) {
	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 = -INF, upper = INF;
	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(ll_[0], ll_[1]), ll_[2]) > max(max(ll1[0], ll1[1]), ll1[2]))
			for (h = 0; h < 3; h++)
				xx_[h] = xx1[h], yy_[h] = yy1[h], ll_[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 *ll_) {
	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 = -INF;
		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(ll_[0], ll_[1]), ll_[2]) > max(max(l1, l2), l3))
					xx_[0] = x1, yy_[0] = y1, ll_[0] = l1, xx_[1] = x2, yy_[1] = y2, ll_[1] = l2, xx_[2] = x3, yy_[2] = y3, ll_[2] = l3;
			}
		}
	}
}

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

	scanf("%d%d", &n, &k);
	for (i = 0; i < n; i++)
		scanf("%lld%lld", &xx[i], &yy[i]);
	if (n == 1 && k >= 2) {
		printf("%lld %lld 1\n", xx[0], yy[0]);
		printf("%lld %lld 1\n", xx[0] - 2, yy[0] - 2);
		if (k >= 3)
			printf("%lld %lld 1\n", xx[0] - 4, yy[0] - 4);
		return 0;
	}
	if (n == 2 && k == 3) {
		if (xx[0] < xx[1])
			printf("%lld %lld 1\n", xx[0] - 1, yy[0]), printf("%lld %lld 1\n", xx[1], yy[1]);
		else if (xx[1] < xx[0])
			printf("%lld %lld 1\n", xx[1] - 1, yy[1]), printf("%lld %lld 1\n", xx[0], yy[0]);
		else if (yy[0] < yy[1])
			printf("%lld %lld 1\n", xx[0], yy[0] - 1), printf("%lld %lld 1\n", xx[1], yy[1]);
		else
			printf("%lld %lld 1\n", xx[1], yy[1] - 1), printf("%lld %lld 1\n", xx[0], yy[0]);
		printf("%d %d 1\n", INF, INF);
		return 0;
	}
	ll_[0] = LINF;
	for (i = 0; i < n; i++)
		ii[i] = i;
	if (k == 1)
		solve1(ii, n, xx_, yy_, ll_);
	else if (k == 2)
		for (u = 0; u < 2; u++) {
			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;
		}
	else if (k == 3) {
		for (u = 0; u < 4; u++) {
			for (i = 0; i < n; i++)
				ii[i] = i;
			sort(ii, 0, n);
			solve3(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;
				xx_[h] -= ll_[h];
			}
		}
#if 0
		for (u = 0; u < 2; u++) {
			for (i = 0; i < n; i++)
				ii[i] = i;
			sort(ii, 0, n);
			solve111(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;
		}
#endif
	}
	for (h = 0; h < k; h++)
		printf("%lld %lld %lld\n", xx_[h], yy_[h], ll_[h]);
	return 0;
}

Compilation message

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

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	24 ms	2176 KB	Output is correct
8	Correct	27 ms	2124 KB	Output is correct
9	Correct	28 ms	2220 KB	Output is correct
10	Correct	26 ms	2176 KB	Output is correct
11	Correct	25 ms	2116 KB	Output is correct

Subtask #2

21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	62 ms	5288 KB	Output is correct
11	Correct	56 ms	5272 KB	Output is correct
12	Correct	58 ms	5248 KB	Output is correct
13	Correct	56 ms	5316 KB	Output is correct
14	Correct	58 ms	5296 KB	Output is correct
15	Correct	58 ms	5340 KB	Output is correct
16	Correct	56 ms	5296 KB	Output is correct
17	Correct	50 ms	4932 KB	Output is correct
18	Correct	49 ms	4704 KB	Output is correct
19	Correct	44 ms	4292 KB	Output is correct
20	Correct	49 ms	4548 KB	Output is correct
21	Correct	58 ms	5320 KB	Output is correct
22	Correct	55 ms	5312 KB	Output is correct
23	Correct	55 ms	5340 KB	Output is correct

Subtask #3

0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Incorrect	0 ms	332 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #4

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	332 KB	Output is correct
2	Correct	2 ms	332 KB	Output is correct
3	Correct	3 ms	332 KB	Output is correct
4	Correct	3 ms	332 KB	Output is correct
5	Correct	3 ms	332 KB	Output is correct
6	Correct	3 ms	332 KB	Output is correct
7	Correct	2 ms	332 KB	Output is correct
8	Correct	3 ms	332 KB	Output is correct
9	Correct	3 ms	332 KB	Output is correct
10	Correct	3 ms	332 KB	Output is correct
11	Correct	2 ms	332 KB	Output is correct
12	Correct	2 ms	332 KB	Output is correct
13	Correct	2 ms	332 KB	Output is correct
14	Correct	2 ms	332 KB	Output is correct
15	Correct	2 ms	332 KB	Output is correct
16	Correct	2 ms	332 KB	Output is correct
17	Correct	2 ms	332 KB	Output is correct
18	Correct	2 ms	332 KB	Output is correct
19	Correct	2 ms	332 KB	Output is correct
20	Correct	2 ms	332 KB	Output is correct
21	Correct	2 ms	332 KB	Output is correct
22	Correct	2 ms	376 KB	Output is correct
23	Correct	2 ms	332 KB	Output is correct
24	Correct	2 ms	332 KB	Output is correct

Subtask #5

0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	332 KB	Output is correct
2	Correct	3 ms	332 KB	Output is correct
3	Correct	2 ms	332 KB	Output is correct
4	Correct	2 ms	332 KB	Output is correct
5	Correct	3 ms	332 KB	Output is correct
6	Correct	2 ms	332 KB	Output is correct
7	Correct	2 ms	332 KB	Output is correct
8	Correct	3 ms	332 KB	Output is correct
9	Correct	2 ms	332 KB	Output is correct
10	Correct	2 ms	332 KB	Output is correct
11	Correct	2 ms	332 KB	Output is correct
12	Correct	3 ms	332 KB	Output is correct
13	Correct	3 ms	332 KB	Output is correct
14	Incorrect	219 ms	4880 KB	Output isn't correct
15	Halted	0 ms	0 KB	-