oj.uz

Submission #213080

# Submission time Handle Problem Language Result Execution time Memory
213080 2020-03-25T01:13:25 Z ainta Hamburg Steak (JOI20_hamburg) C++17
3 / 100
 208 ms 4376 KB 
#include<cstdio>
#include<algorithm>
#define N_ 201000
using namespace std;
int n, K, C[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", a.x, 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]++;
	}
}
int main() {
	int i;
	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);
	}
	Do(0);

}

Compilation message

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

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 288 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 288 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Incorrect 3 ms 360 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Incorrect 3 ms 384 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 141 ms 4216 KB Output is correct
6 Correct 145 ms 4216 KB Output is correct
7 Correct 141 ms 4216 KB Output is correct
8 Correct 140 ms 4216 KB Output is correct

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 201 ms 4196 KB Output is correct
6 Correct 195 ms 4376 KB Output is correct
7 Incorrect 208 ms 4204 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 288 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 288 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Incorrect 3 ms 360 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Incorrect 3 ms 384 KB Output isn't correct
8 Halted 0 ms 0 KB -