oj.uz

Submission #493310

# Submission time Handle Problem Language Result Execution time Memory
493310 2021-12-10T21:47:27 Z rainboy Izvanzemaljci (COI21_izvanzemaljci) C
56 / 100
 3000 ms 8772 KB 
#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]);
		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

# 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 280 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 29 ms 2324 KB Output is correct
8 Correct 26 ms 2316 KB Output is correct
9 Correct 36 ms 2288 KB Output is correct
10 Correct 29 ms 2340 KB Output is correct
11 Correct 28 ms 2268 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 332 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 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 1 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 67 ms 5388 KB Output is correct
11 Correct 84 ms 5440 KB Output is correct
12 Correct 60 ms 5572 KB Output is correct
13 Correct 69 ms 5504 KB Output is correct
14 Correct 65 ms 5452 KB Output is correct
15 Correct 60 ms 5448 KB Output is correct
16 Correct 59 ms 5448 KB Output is correct
17 Correct 57 ms 5044 KB Output is correct
18 Correct 54 ms 4988 KB Output is correct
19 Correct 61 ms 4568 KB Output is correct
20 Correct 47 ms 4828 KB Output is correct
21 Correct 59 ms 5512 KB Output is correct
22 Correct 59 ms 5424 KB Output is correct
23 Correct 64 ms 5484 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 Incorrect 0 ms 204 KB Unexpected end of file - int64 expected
3 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 452 KB Output is correct
2 Correct 5 ms 332 KB Output is correct
3 Correct 6 ms 448 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 5 ms 332 KB Output is correct
6 Correct 5 ms 332 KB Output is correct
7 Correct 6 ms 460 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 460 KB Output is correct
11 Correct 7 ms 424 KB Output is correct
12 Correct 6 ms 332 KB Output is correct
13 Correct 7 ms 432 KB Output is correct
14 Correct 5 ms 420 KB Output is correct
15 Correct 7 ms 424 KB Output is correct
16 Correct 5 ms 332 KB Output is correct
17 Correct 7 ms 332 KB Output is correct
18 Correct 5 ms 424 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 5 ms 332 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 332 KB Output is correct
2 Correct 6 ms 332 KB Output is correct
3 Correct 7 ms 452 KB Output is correct
4 Correct 6 ms 332 KB Output is correct
5 Correct 6 ms 548 KB Output is correct
6 Correct 5 ms 332 KB Output is correct
7 Correct 7 ms 408 KB Output is correct
8 Correct 7 ms 460 KB Output is correct
9 Correct 6 ms 424 KB Output is correct
10 Correct 6 ms 428 KB Output is correct
11 Correct 6 ms 460 KB Output is correct
12 Correct 9 ms 332 KB Output is correct
13 Correct 6 ms 448 KB Output is correct
14 Execution timed out 3059 ms 8772 KB Time limit exceeded
15 Halted 0 ms 0 KB -