oj.uz

답안 #493304

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
493304 2021-12-10T20:34:22 Z rainboy Izvanzemaljci (COI21_izvanzemaljci) C
21 / 100
 58 ms 7380 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]);
		printf("%lld %lld 1\n", xx[0] - 2, yy[0] - 2);
		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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Extra information in the output file
2 Halted 0 ms 0 KB -

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 55 ms 5228 KB Output is correct
11 Correct 58 ms 7348 KB Output is correct
12 Correct 58 ms 7288 KB Output is correct
13 Correct 58 ms 7380 KB Output is correct
14 Correct 57 ms 7364 KB Output is correct
15 Correct 55 ms 7364 KB Output is correct
16 Correct 55 ms 7328 KB Output is correct
17 Correct 51 ms 6732 KB Output is correct
18 Correct 49 ms 6552 KB Output is correct
19 Correct 46 ms 5976 KB Output is correct
20 Correct 46 ms 6412 KB Output is correct
21 Correct 55 ms 7360 KB Output is correct
22 Correct 57 ms 7232 KB Output is correct
23 Correct 56 ms 7240 KB Output is correct

Subtask #3
0 / 12.0

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