Submission #671312

#	Time	Username	Problem	Language	Result	Execution time	Memory
671312		rainboy	Hamburg Steak (JOI20_hamburg)	C11	15 / 100	1492 ms	6604 KiB

hamburg

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
 
#define N	200000
#define K	4
#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; }
 
long long xxl[N], xxr[N], yyl[N], yyr[N], xx[K], yy[K]; int n, k;
 
int pierced(int i, int h_) {
	int h;
 
	for (h = 0; h < h_; h++)
		if (xxl[i] <= xx[h] && xx[h] <= xxr[i] && yyl[i] <= yy[h] && yy[h] <= yyr[i])
			return 1;
	return 0;
}
 
void solve(int h_) {
	int h, i;
	long long xl, xr, yl, yr;
 
	xl = INF, xr = -1, yl = INF, yr = -1;
	for (i = 0; i < n; i++)
		if (!pierced(i, h_))
			xl = min(xl, xxr[i]), xr = max(xr, xxl[i]), yl = min(yl, yyr[i]), yr = max(yr, yyl[i]);
	if (xl == INF) {
		for (h = h_; h < k; h++)
			xx[h] = 1, yy[h] = 1;
		for (h = 0; h < k; h++)
			printf("%lld %lld\n", xx[h], yy[h]);
		exit(0);
	} else if (h_ < k) {
		xx[h_] = xl, yy[h_] = yl, solve(h_ + 1);
		xx[h_] = xl, yy[h_] = yr, solve(h_ + 1);
		xx[h_] = xr, yy[h_] = yl, solve(h_ + 1);
		xx[h_] = xr, yy[h_] = yr, solve(h_ + 1);
	}
}
 
long long ll[N], rr[N]; int ii0[N], ii1[N], ii2[N], n0, n1, n2; long long xl, xr, yl, yr, z1, z2, z3, z4;
 
long long idx(long long x, long long y) {
	if (y == yl)
		return x - xl;
	if (x == xr)
		return z1 + y - yl;
	if (y == yr)
		return z2 + xr - x;
	if (x == xl)
		return z3 + yr - y;
	return -1;
}
 
void get_min_max(int h_, long long *xl_, long long *yl_, long long *xr_, long long *yr_) {
	int h, i, i_, pierced;
 
	*xl_ = INF, *xr_ = -1, *yl_ = INF, *yr_ = -1;
	for (i = 0; i < n0; i++) {
		i_ = ii0[i], pierced = 0;
		for (h = 0; h < h_; h++) {
			long long z = idx(xx[h], yy[h]);
 
			if (ll[i_] <= z && z <= rr[i_] || ll[i_] <= z4 + z && z4 + z <= rr[i_]) {
				pierced = 1;
				break;
			}
		}
		if (!pierced)
			*xl_ = min(*xl_, xxr[i_]), *xr_ = max(*xr_, xxl[i_]), *yl_ = min(*yl_, yyr[i_]), *yr_ = max(*yr_, yyl[i_]);
	}
	for (i = 0; i < n1; i++) {
		i_ = ii1[i], pierced = 0;
		for (h = 0; h < h_; h++)
			if (ll[i_] <= xx[h] && xx[h] <= rr[i_]) {
				pierced = 1;
				break;
			}
		if (!pierced)
			*xl_ = min(*xl_, xxr[i_]), *xr_ = max(*xr_, xxl[i_]), *yl_ = min(*yl_, yyr[i_]), *yr_ = max(*yr_, yyl[i_]);
	}
	for (i = 0; i < n2; i++) {
		i_ = ii2[i], pierced = 0;
		for (h = 0; h < h_; h++)
			if (ll[i_] <= yy[h] && yy[h] <= rr[i_]) {
				pierced = 1;
				break;
			}
		if (!pierced)
			*xl_ = min(*xl_, xxr[i_]), *xr_ = max(*xr_, xxl[i_]), *yl_ = min(*yl_, yyr[i_]), *yr_ = max(*yr_, yyl[i_]);
	}
}
 
void solve_(int h_) {
	int h, i;
	long long xl_, yl_, xr_, yr_;
 
	if (h_ > 0 && idx(xx[h_ - 1], yy[h_ - 1]) == -1)
		return;
	get_min_max(h_, &xl_, &yl_, &xr_, &yr_);
	if (xl_ == INF) {
		for (h = h_; h < k; h++)
			xx[h] = 1, yy[h] = 1;
		for (h = 0; h < k; h++)
			printf("%lld %lld\n", xx[h], yy[h]);
		exit(0);
	} else if (h_ == 0) {
		xx[h_] = xl_;
		for (i = 0; i < n; i++)
			yy[h_] = yyl[i], solve_(h_ + 1);
	} else if (h_ < k) {
		xx[h_] = xl_, yy[h_] = yl_, solve_(h_ + 1);
		xx[h_] = xl_, yy[h_] = yr_, solve_(h_ + 1);
		xx[h_] = xr_, yy[h_] = yl_, solve_(h_ + 1);
		xx[h_] = xr_, yy[h_] = yr_, solve_(h_ + 1);
	}
}
 
int main() {
	int i;
	long long l, r;
 
	scanf("%d%d", &n, &k);
	for (i = 0; i < n; i++)
		scanf("%lld%lld%lld%lld", &xxl[i], &yyl[i], &xxr[i], &yyr[i]);
	solve(0);
	xl = INF, xr = -1, yl = INF, yr = -1;
	for (i = 0; i < n; i++)
		xl = min(xl, xxr[i]), xr = max(xr, xxl[i]), yl = min(yl, yyr[i]), yr = max(yr, yyl[i]);
	assert(k == 4 && xl < xr && yl < yr);
	z1 = xr - xl, z2 = z1 + yr - yl, z3 = z2 + xr - xl, z4 = z3 + yr - yl;
	for (i = 0; i < n; i++)
		xxl[i] = max(xxl[i], xl), xxr[i] = min(xxr[i], xr), yyl[i] = max(yyl[i], yl), yyr[i] = min(yyr[i], yr);
	for (i = 0; i < n; i++)
		if (xl < xxl[i] && xxr[i] < xr && yyl[i] == yl && yyr[i] == yr)
			ll[i] = xxl[i], rr[i] = xxr[i], ii1[n1++] = i;
		else if (yl < yyl[i] && yyr[i] < yr && xxl[i] == xl && xxr[i] == xr)
			ll[i] = yyl[i], rr[i] = yyr[i], ii2[n2++] = i;
		else {
			l = INF, r = -1;
			if (yyl[i] == yl) {
				l = min(l, xxl[i] - xl), r = max(r, xxr[i] - xl);
				if (xxl[i] == xl)
					l += z4, r += z4;
			}
			if (xxr[i] == xr) {
				l = min(l, z1 + yyl[i] - yl), r = max(r, z1 + yyr[i] - yl);
				if (xxl[i] == xl && yyl[i] == yl)
					l += z4, r += z4;
			}
			if (yyr[i] == yr)
				l = min(l, z2 + xr - xxr[i]), r = max(r, z2 + xr - xxl[i]);
			if (xxl[i] == xl)
				l = min(l, z3 + yr - yyr[i]), r = max(r, z3 + yr - yyl[i]);
			ll[i] = l, rr[i] = r, ii0[n0++] = i;
		}
	solve_(0);
	return 0;
}

Compilation message (stderr)

hamburg.c: In function 'get_min_max':
hamburg.c:68:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   68 |    if (ll[i_] <= z && z <= rr[i_] || ll[i_] <= z4 + z && z4 + z <= rr[i_]) {
      |        ~~~~~~~~~~~~^~~~~~~~~~~~~~
hamburg.c: In function 'main':
hamburg.c:127:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |  scanf("%d%d", &n, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~
hamburg.c:129:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |   scanf("%lld%lld%lld%lld", &xxl[i], &yyl[i], &xxr[i], &yyr[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 1 / 1
• Subtask 3: 3 / 3
• Subtask 4: 0 / 6
• Subtask 5: 1 / 1
• Subtask 6: 3 / 3
• Subtask 7: 6 / 6
• Subtask 8: 0 / 79