oj.uz

Submission #493311

# Submission time Handle Problem Language Result Execution time Memory
493311 2021-12-10T21:48:39 Z rainboy Izvanzemaljci (COI21_izvanzemaljci) C
68 / 100
 3000 ms 7176 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]);
		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

# 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 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

# 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 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

# 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 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -