oj.uz

Submission #493300

# Submission time Handle Problem Language Result Execution time Memory
493300 2021-12-10T20:17:46 Z rainboy Izvanzemaljci (COI21_izvanzemaljci) C
5 / 100
 29 ms 2892 KB 
#include <stdio.h>
#include <sys/time.h>

#define N	100000
#define INF	0x7fffffff
#define X	3000000000

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

unsigned int Z = 12345;

int rand_() {
	return (Z *= 3) >> 1;
}

int xx[N], yy[N], n;

void solve1(long long *xx_, long long *yy_, long long *ll_) {
	int i, 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;

		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 int yld[N], ylu[N], yrd[N], yru[N];
	int i, 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]]) {
			int 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("%d%d", &xx[i], &yy[i]);
	xx_[0] = X - 10, yy_[0] = X - 10, ll_[0] = INF;
	xx_[1] = X - 20, yy_[1] = X - 20, ll_[1] = 1;
	xx_[2] = X - 30, yy_[2] = X - 30, ll_[2] = 1;
	solve1(xx_, yy_, ll_);
	if (k == 2)
		for (u = 0; u < 2; u++) {
			int 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:87:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |  scanf("%d%d", &n, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~
izvanzemaljci.c:89:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |   scanf("%d%d", &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 952 KB Output is correct
8 Correct 24 ms 1044 KB Output is correct
9 Correct 26 ms 964 KB Output is correct
10 Correct 27 ms 976 KB Output is correct
11 Correct 25 ms 964 KB Output is correct

Subtask #2
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 Incorrect 29 ms 2892 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Incorrect 0 ms 204 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -