답안 #493311

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
493311	2021-12-10T21:48:39 Z	rainboy	Izvanzemaljci (COI21_izvanzemaljci)	C	68 / 100	3000 ms	7176 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];
			}
		}
		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;
		}
	}
	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

#	결과	실행 시간	메모리	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	23 ms	2152 KB	Output is correct
8	Correct	23 ms	2192 KB	Output is correct
9	Correct	22 ms	2124 KB	Output is correct
10	Correct	23 ms	2124 KB	Output is correct
11	Correct	23 ms	2124 KB	Output is correct

Subtask #2

21.0 / 21.0

#	결과	실행 시간	메모리	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	0 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	63 ms	5332 KB	Output is correct
11	Correct	55 ms	5344 KB	Output is correct
12	Correct	55 ms	5284 KB	Output is correct
13	Correct	62 ms	5416 KB	Output is correct
14	Correct	55 ms	5276 KB	Output is correct
15	Correct	54 ms	5284 KB	Output is correct
16	Correct	54 ms	5284 KB	Output is correct
17	Correct	47 ms	4840 KB	Output is correct
18	Correct	45 ms	4704 KB	Output is correct
19	Correct	45 ms	4272 KB	Output is correct
20	Correct	43 ms	4664 KB	Output is correct
21	Correct	54 ms	5272 KB	Output is correct
22	Correct	53 ms	5316 KB	Output is correct
23	Correct	56 ms	5348 KB	Output is correct

Subtask #3

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 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	0 ms	332 KB	Output is correct
9	Correct	0 ms	332 KB	Output is correct
10	Correct	0 ms	332 KB	Output is correct
11	Correct	0 ms	332 KB	Output is correct
12	Correct	0 ms	332 KB	Output is correct
13	Correct	0 ms	332 KB	Output is correct
14	Correct	0 ms	332 KB	Output is correct
15	Correct	0 ms	332 KB	Output is correct
16	Correct	0 ms	276 KB	Output is correct
17	Correct	1 ms	332 KB	Output is correct
18	Correct	0 ms	332 KB	Output is correct
19	Correct	0 ms	332 KB	Output is correct
20	Correct	0 ms	332 KB	Output is correct
21	Correct	0 ms	332 KB	Output is correct
22	Correct	0 ms	332 KB	Output is correct
23	Correct	0 ms	332 KB	Output is correct
24	Correct	0 ms	332 KB	Output is correct
25	Correct	0 ms	332 KB	Output is correct
26	Correct	0 ms	332 KB	Output is correct

Subtask #4

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	332 KB	Output is correct
2	Correct	6 ms	428 KB	Output is correct
3	Correct	5 ms	332 KB	Output is correct
4	Correct	5 ms	332 KB	Output is correct
5	Correct	5 ms	332 KB	Output is correct
6	Correct	6 ms	332 KB	Output is correct
7	Correct	5 ms	432 KB	Output is correct
8	Correct	6 ms	332 KB	Output is correct
9	Correct	5 ms	332 KB	Output is correct
10	Correct	5 ms	332 KB	Output is correct
11	Correct	5 ms	332 KB	Output is correct
12	Correct	5 ms	380 KB	Output is correct
13	Correct	5 ms	332 KB	Output is correct
14	Correct	4 ms	332 KB	Output is correct
15	Correct	4 ms	332 KB	Output is correct
16	Correct	5 ms	416 KB	Output is correct
17	Correct	4 ms	376 KB	Output is correct
18	Correct	4 ms	332 KB	Output is correct
19	Correct	4 ms	332 KB	Output is correct
20	Correct	4 ms	332 KB	Output is correct
21	Correct	6 ms	332 KB	Output is correct
22	Correct	6 ms	332 KB	Output is correct
23	Correct	5 ms	332 KB	Output is correct
24	Correct	6 ms	460 KB	Output is correct

Subtask #5

0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	332 KB	Output is correct
2	Correct	5 ms	332 KB	Output is correct
3	Correct	5 ms	332 KB	Output is correct
4	Correct	5 ms	332 KB	Output is correct
5	Correct	5 ms	428 KB	Output is correct
6	Correct	5 ms	332 KB	Output is correct
7	Correct	5 ms	428 KB	Output is correct
8	Correct	5 ms	332 KB	Output is correct
9	Correct	5 ms	432 KB	Output is correct
10	Correct	5 ms	424 KB	Output is correct
11	Correct	6 ms	332 KB	Output is correct
12	Correct	5 ms	332 KB	Output is correct
13	Correct	5 ms	376 KB	Output is correct
14	Execution timed out	3073 ms	7176 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-