oj.uz

답안 #493303

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
493303 2021-12-10T20:33:40 Z rainboy Izvanzemaljci (COI21_izvanzemaljci) C
5 / 100
 25 ms 1832 KB 
#include <stdio.h>
#include <sys/time.h>

#define N	100000
#define INF	0x3f3f3f3f3f3f3f3fLL

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

	xmn = INF, xmx = -INF, ymn = INF, ymx = -INF;
	for (i = 0; i < n; 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], ylu[N], yrd[N], yru[N];
	int i;
	long long x1_, y1_, l1_, x2_, y2_, l2_;

	for (i = 0; i < n; i++) {
		yld[i] = min(i == 0 ? INF : yld[i - 1], yy[ii[i]]);
		ylu[i] = max(i == 0 ? -INF : ylu[i - 1], yy[ii[i]]);
	}
	for (i = n - 1; i >= 0; i--) {
		yrd[i] = min(i + 1 == n ? INF : yrd[i + 1], yy[ii[i]]);
		yru[i] = max(i + 1 == n ? -INF : yru[i + 1], yy[ii[i]]);
	}
	x1_ = y1_ = x2_ = y2_ = -1, l1_ = l2_ = INF;
	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(l1_, l2_) > max(l1, l2))
				x1_ = x1, y1_ = y1, l1_ = l1, x2_ = x2, y2_ = y2, l2_ = 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() {
	xx[0] = yy[0] = n;
}

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

	scanf("%d%d", &n, &k);
	for (i = 0; i < n; i++)
		scanf("%lld%lld", &xx[i], &yy[i]);
	if (n == 1) {
		printf("%lld %lld 1\n", xx[0], yy[0]);
		return 0;
	}
	ll_[0] = INF;
	if (k == 1)
		solve1(xx_, yy_, ll_);
	else if (k == 2)
		for (u = 0; u < 2; u++) {
			long long tmp;

			for (i = 0; i < n; i++)
				ii[i] = i;
			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;
		}
	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 'main':
izvanzemaljci.c:89:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |  scanf("%d%d", &n, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~
izvanzemaljci.c:91:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |   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 24 ms 1728 KB Output is correct
8 Correct 23 ms 1716 KB Output is correct
9 Correct 25 ms 1792 KB Output is correct
10 Correct 24 ms 1832 KB Output is correct
11 Correct 24 ms 1732 KB Output is correct

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 332 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Integer 4557430888798830399 violates the range [1, 2*10^9]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Integer 4557430888798830399 violates the range [1, 2*10^9]
2 Halted 0 ms 0 KB -