oj.uz

Submission #213088

# Submission time Handle Problem Language Result Execution time Memory
213088 2020-03-25T01:46:11 Z ainta Hamburg Steak (JOI20_hamburg) C++17
6 / 100
 172 ms 4344 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] = { Ax, yy3 };
	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:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   62 |  scanf("%d%d", &n, &K);
      |  ~~~~~^~~~~~~~~~~~~~~~
hamburg.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |   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 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 #2
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 #3
0 / 3.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 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Incorrect 2 ms 384 KB Unexpected end of file - int32 expected
9 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 3 ms 372 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Incorrect 3 ms 384 KB Unexpected end of file - int32 expected
9 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 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 139 ms 4216 KB Output is correct
6 Correct 145 ms 4344 KB Output is correct
7 Correct 143 ms 4216 KB Output is correct
8 Correct 154 ms 4216 KB Output is correct

Subtask #6
3.0 / 3.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 172 ms 4232 KB Output is correct
6 Correct 148 ms 4240 KB Output is correct
7 Correct 161 ms 4176 KB Output is correct
8 Correct 153 ms 4192 KB Output is correct

Subtask #7
0 / 6.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 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Incorrect 2 ms 384 KB Unexpected end of file - int32 expected
9 Halted 0 ms 0 KB -

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 3 ms 372 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Incorrect 3 ms 384 KB Unexpected end of file - int32 expected
9 Halted 0 ms 0 KB -