Submission #671288

#	Time	Username	Problem	Language	Result	Execution time	Memory
671288		rainboy	Hamburg Steak (JOI20_hamburg)	C11	15 / 100	245 ms	6776 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 xr - xl + y - yl;
	if (y == yr)
		return xr - xl + yr - yl + xr - x;
	if (x == xl)
		return xr - xl + yr - yl + xr - xl + yr - y;
	return -1;
}

long long xl_, yl_, xr_, yr_;

void get_min_max(int h_) {
	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 && rr[i_] <= z4 + z) {
				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;

	if (h_ == 0 || idx(xx[h_ - 1], yy[h_ - 1]) == -1)
		return;
	get_min_max(h_);
	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 {
			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 (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:70:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   70 |    if (ll[i_] <= z && z <= rr[i_] || ll[i_] <= z4 + z && rr[i_] <= z4 + z) {
      |        ~~~~~~~~~~~~^~~~~~~~~~~~~~
hamburg.c: In function 'main':
hamburg.c:130:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |  scanf("%d%d", &n, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~
hamburg.c:132:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |   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