Submission #216742

#	Time	Username	Problem	Language	Result	Execution time	Memory
216742		ainta	Hamburg Steak (JOI20_hamburg)	C++17	15 / 100	628 ms	7480 KiB

hamburg

#include<cstdio>
#include<algorithm>
#define N_ 401000
using namespace std;
int n, K, C[N_], X[N_], Y[N_];
struct Rect {
	int bx, by, ex, ey;
}w[N_];
struct point {
	int x, y;
}U[5];
bool Inside(Rect a, point b) {
	return a.bx <= b.x&&b.x <= a.ex&&a.by <= b.y&&b.y <= a.ey;
}
void Print(point a) {
	printf("%d %d\n", X[a.x], Y[a.y]);
}
void Do(int pv) {
	int i;
	if (pv) {
		for (i = 1; i <= n; i++)if (Inside(w[i], U[pv - 1]))C[i]++;
	}
	if (pv == K) {
		for (i = 1; i <= n; i++) if (!C[i])break;
		if (i > n) {
			for (i = 0; i < K; i++)Print(U[i]);
			exit(0);
		}
		for (i = 1; i <= n; i++)if (Inside(w[i], U[pv - 1]))C[i]--;
		return;
	}
	int Ax = 0, Bx = 1e9, Ay = 0, By = 1e9;
	for (i = 1; i <= n; i++) {
		if (C[i])continue;
		Ax = max(Ax, w[i].bx);
		Ay = max(Ay, w[i].by);
		Bx = min(Bx, w[i].ex);
		By = min(By, w[i].ey);
	}
	int yy1 = 0, yy2 = 1e9, yy3 = 0, yy4 = 1e9;
	for (i = 1; i <= n; i++) {
		if (C[i])continue;
		if (w[i].bx <= Bx) {
			yy1 = max(yy1, w[i].by);
			yy2 = min(yy2, w[i].ey);
		}
		if (w[i].ex >= Ax) {
			yy3 = max(yy3, w[i].by);
			yy4 = min(yy4, w[i].ey);
		}
	}
	U[pv] = { Bx, yy1 };
	Do(pv + 1);
	U[pv] = { Bx, yy2 };
	Do(pv + 1);
	U[pv] = { Ax, yy3 };
	Do(pv + 1);
	U[pv] = { Ax, yy4 };
	Do(pv + 1);
	if (pv) {
		for (i = 1; i <= n; i++)if (Inside(w[i], U[pv - 1]))C[i]--;
	}
}
void ReNum(int &a, int *b, int c) {
	a = lower_bound(b + 1, b + c + 1, a) - b;
}

int Next[4][N_], CX = 0, CY = 0, BBx, EEx, BBy, EEy, T[4];

void Go(int pv, int a) {
	T[pv] = a;
	int t = Next[pv][a] - n*2;
	if (t <= 0)return;
	if (pv == 3) {
		if (t < T[0]) return;
		if ((BBy <= T[0] && T[0] <= EEy) || (BBy <= 2 * n + 1 - T[2] && 2 * n + 1 - T[2] <= EEy)) {
			if ((BBx <= T[1] && T[1] <= EEx) || (BBx <= 2 * n + 1 - T[3] && 2 * n + 1 - T[3] <= EEx)) {
				U[0].y = T[0];
				U[1].x = T[1];
				U[2].y = 2 * n + 1 - T[2];
				U[3].x = 2 * n + 1 - T[3];
				for (int i = 0; i < K; i++)Print(U[i]);
				exit(0);
			}
		}

		return;
	}
	Go(pv + 1, t);
	if (pv == 0) {
		if (t > EEx) {
			Go(pv + 1, EEx);
		}
	}
	if (pv == 1) {
		if (t > 2*n-BBy+1) {
			Go(pv + 1, BBy);
		}
	}
	if (pv == 2) {
		if (t > 2 * n - BBx + 1) {
			Go(pv + 1, BBx);
		}
	}
}

int main() {
	int i, j;
	scanf("%d%d", &n, &K);
	for (i = 1; i <= n; i++) {
		scanf("%d%d%d%d", &w[i].bx, &w[i].by, &w[i].ex, &w[i].ey);
		X[++CX] = w[i].bx, X[++CX] = w[i].ex;
		Y[++CY] = w[i].by, Y[++CY] = w[i].ey;
	}
	sort(X + 1, X + CX + 1);
	sort(Y + 1, Y + CY + 1);
	for (i = 1; i <= n; i++) {
		ReNum(w[i].bx, X, CX);
		ReNum(w[i].ex, X, CX);
		ReNum(w[i].by, Y, CY);
		ReNum(w[i].ey, Y, CY);
	}
	Do(0);
	int Ax = 0, Bx = 1e9, Ay = 0, By = 1e9;
	for (i = 1; i <= n; i++) {
		Ax = max(Ax, w[i].bx);
		Ay = max(Ay, w[i].by);
		Bx = min(Bx, w[i].ex);
		By = min(By, w[i].ey);
	}
	if (Ax <= Bx || Ay <= By) {
		while (1) {}
	}
	U[0].x = Bx, U[1].y = Ay, U[2].x = Ax, U[3].y = By;
	BBx = 1, EEx = CX;
	BBy = 1, EEy = CY;
	for (i = 0; i < 4; i++)for (j = 1; j <= n + n; j++)Next[i][j] = 4 * n;
	for (i = 1; i <= n; i++) {
		int ck = 0, c = 0;
		if (w[i].bx <= Bx)ck |= 1, c++;
		if (w[i].ey >= Ay)ck |= 2, c++;
		if (w[i].ex >= Ax)ck |= 4, c++;
		if (w[i].by <= By)ck |= 8, c++;
		if (c >= 3)continue;
		if (ck == 0) {
			while (1) {}
		}
		if (ck == 1) {
			Next[0][w[i].by - 1] = min(Next[0][w[i].by - 1], w[i].ey);
		}
		if (ck == 2) {
			Next[1][w[i].bx - 1] = min(Next[1][w[i].ex - 1], w[i].ex);
		}
		if (ck == 4) {
			Next[2][CY - w[i].ey] = min(Next[2][CY - w[i].ey], CY - w[i].by + 1);
		}
		if (ck == 8) {
			Next[3][CX - w[i].ex] = min(Next[3][CX - w[i].ex], CX - w[i].bx + 1);
		}
		if (ck == 3) {
			Next[0][w[i].by - 1] = min(Next[0][w[i].by - 1], CY + w[i].ex);
		}
		if (ck == 6) {
			Next[1][w[i].bx - 1] = min(Next[1][w[i].bx - 1], CX + CY - w[i].by + 1);
		}
		if (ck == 12) {
			Next[2][CY - w[i].ey] = min(Next[2][CY - w[i].ey], CY + CX - w[i].bx + 1);
		}
		if (ck == 9) {
			Next[3][CX - w[i].ex] = min(Next[3][CX - w[i].ex], CX + w[i].ey);
		}
		if (ck == 5) {
			BBy = max(BBy, w[i].by);
			EEy = min(EEy, w[i].ey);
		}
		if (ck == 10) {
			BBx = max(BBx, w[i].bx);
			EEx = min(EEx, w[i].ex);
		}
	}
	for (i = 0; i < 4; i++) {
		for (j = n + n - 1; j >= 0; j--) {
			Next[i][j] = min(Next[i][j], Next[i][j + 1]);
		}
	}
	for (i = 0; i < 4; i++) {
		for (j = 1; j <= n + n; j++) {
			Next[i][j] = min(Next[i][j], Next[(i + 1) % 4][0] + 2*n);
		}
	}
	for (i = 1; i <= CY; i++) {
		Go(0, i);
	}
}

Compilation message (stderr)

hamburg.cpp: In function 'int main()':
hamburg.cpp:109:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  109 |  scanf("%d%d", &n, &K);
      |  ~~~~~^~~~~~~~~~~~~~~~
hamburg.cpp:111:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  111 |   scanf("%d%d%d%d", &w[i].bx, &w[i].by, &w[i].ex, &w[i].ey);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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