oj.uz

Submission #493476

# Submission time Handle Problem Language Result Execution time Memory
493476 2021-12-11T15:02:22 Z rainboy Izvanzemaljci (COI21_izvanzemaljci) C
35 / 100
 3000 ms 8828 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, 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++) {
		i_ = ii[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 + 1], 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 solve21(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, r;
	long long tmp;

	scanf("%d%d", &n, &k);
	for (i = 0; i < n; i++) {
		scanf("%lld%lld", &xx[i], &yy[i]);
		ii[i] = i;
	}
	ll_[0] = LINF;
	if (k == 1)
		solve1(ii, n, xx_, yy_, ll_);
	else if (k == 2)
		for (r = 0; r < 2; r++) {
			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 (r = 0; r < 4; r++) {
			for (i = 0; i < n; i++)
				ii[i] = i;
			sort(ii, 0, n);
			solve21(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 (r = 0; r < 2; r++) {
			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 'solve21':
izvanzemaljci.c:102:58: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  102 |   if (ll1[0] == LINF || ll1[1] == LINF || ll1[2] != LINF && max(ll1[0], ll1[1]) < ll1[2])
      |                                           ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
izvanzemaljci.c: In function 'main':
izvanzemaljci.c:149:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |  scanf("%d%d", &n, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~
izvanzemaljci.c:151:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |   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 1 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 27 ms 4204 KB Output is correct
8 Correct 26 ms 4196 KB Output is correct
9 Correct 29 ms 4216 KB Output is correct
10 Correct 30 ms 4144 KB Output is correct
11 Correct 28 ms 4184 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Integer 4557430888798830399 violates the range [1, 2*10^9]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 332 KB Integer 4557430888798830399 violates the range [1, 2*10^9]
2 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.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 6 ms 332 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 6 ms 332 KB Output is correct
6 Correct 5 ms 332 KB Output is correct
7 Correct 5 ms 332 KB Output is correct
8 Correct 6 ms 332 KB Output is correct
9 Correct 9 ms 452 KB Output is correct
10 Correct 6 ms 332 KB Output is correct
11 Correct 8 ms 332 KB Output is correct
12 Correct 6 ms 332 KB Output is correct
13 Correct 5 ms 436 KB Output is correct
14 Correct 7 ms 420 KB Output is correct
15 Correct 5 ms 332 KB Output is correct
16 Correct 5 ms 424 KB Output is correct
17 Correct 6 ms 332 KB Output is correct
18 Correct 6 ms 332 KB Output is correct
19 Correct 5 ms 332 KB Output is correct
20 Correct 5 ms 424 KB Output is correct
21 Correct 7 ms 332 KB Output is correct
22 Correct 7 ms 424 KB Output is correct
23 Correct 6 ms 432 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 416 KB Output is correct
2 Correct 6 ms 332 KB Output is correct
3 Correct 8 ms 424 KB Output is correct
4 Correct 7 ms 460 KB Output is correct
5 Correct 6 ms 332 KB Output is correct
6 Correct 6 ms 452 KB Output is correct
7 Correct 6 ms 448 KB Output is correct
8 Correct 6 ms 332 KB Output is correct
9 Correct 6 ms 332 KB Output is correct
10 Correct 6 ms 456 KB Output is correct
11 Correct 5 ms 460 KB Output is correct
12 Correct 6 ms 332 KB Output is correct
13 Correct 5 ms 452 KB Output is correct
14 Execution timed out 3053 ms 8828 KB Time limit exceeded
15 Halted 0 ms 0 KB -