oj.uz

Submission #787381

# Submission time Handle Problem Language Result Execution time Memory
787381 2023-07-19T06:38:04 Z 박상훈(#10032) Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 1080 ms 27460 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr int INF = 1e9 + 100;

struct Rect{
	int x1, y1, x2, y2;
	Rect(){}
	Rect(int _x1, int _y1, int _x2, int _y2): x1(_x1), y1(_y1), x2(_x2), y2(_y2) {}

	void read(){
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
	}
	bool in(int x, int y){
		return x1 <= x && x <= x2 && y1 <= y && y <= y2;
	}
};

vector<pair<int, int>> ans;

void solve(vector<Rect> V, int k){
	if (k==0){
		if (!V.empty()) return;
		for (auto &[x, y]:ans) printf("%d %d\n", x, y);
		exit(0);
	}

	int lx = INF, rx = -INF, ly = INF, ry = -INF;
	for (auto &[x1, y1, x2, y2]:V){
		lx = min(lx, x2);
		rx = max(rx, x1);
		ly = min(ly, y2);
		ry = max(ry, y1);
	}

	if (V.empty()) lx = rx = ly = ry = 1;

	vector<pair<int, int>> C = {{lx, ly}, {lx, ry}, {rx, ly}, {rx, ry}};
	if (k==4){
		for (auto &[x1, y1, x2, y2]:V){
			C.emplace_back(x1, y1);
			// C.emplace_back(x1, y2);
			// C.emplace_back(x2, y1);
			// C.emplace_back(x2, y2);
		}
	}
	for (auto &[x, y]:C){
		vector<Rect> nV;
		for (auto &R:V) if (!R.in(x, y)) nV.push_back(R);

		ans.emplace_back(x, y);
		solve(nV, k-1);
		ans.pop_back();
	}
}

int main(){
	int n, k;
	scanf("%d %d", &n, &k);
	
	vector<Rect> V(n);
	for (int i=0;i<n;i++) V[i].read();

	solve(V, k);

	printf("failed\n");
	return 0;
}

Compilation message

hamburg.cpp: In function 'int main()':
hamburg.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |  scanf("%d %d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~
hamburg.cpp: In member function 'void Rect::read()':
hamburg.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |   scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

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

Subtask #2
1.0 / 1.0

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

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 2 ms 564 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 1 ms 596 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 436 KB Output is correct
2 Correct 1 ms 440 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 436 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 540 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 3 ms 652 KB Output is correct
14 Incorrect 1080 ms 700 KB Expected integer, but "failed" found
15 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 73 ms 8076 KB Output is correct
6 Correct 72 ms 8048 KB Output is correct
7 Correct 70 ms 8056 KB Output is correct
8 Correct 70 ms 8000 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 436 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 71 ms 9844 KB Output is correct
6 Correct 71 ms 9568 KB Output is correct
7 Correct 70 ms 9732 KB Output is correct
8 Correct 81 ms 18368 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 2 ms 564 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 73 ms 10628 KB Output is correct
14 Correct 69 ms 10768 KB Output is correct
15 Correct 68 ms 9548 KB Output is correct
16 Correct 67 ms 9584 KB Output is correct
17 Correct 71 ms 11980 KB Output is correct
18 Correct 67 ms 9436 KB Output is correct
19 Correct 72 ms 12384 KB Output is correct
20 Correct 76 ms 16000 KB Output is correct
21 Correct 192 ms 27460 KB Output is correct
22 Correct 103 ms 18916 KB Output is correct
23 Correct 94 ms 22212 KB Output is correct
24 Correct 109 ms 25012 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 436 KB Output is correct
2 Correct 1 ms 440 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 436 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 540 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 3 ms 652 KB Output is correct
14 Incorrect 1080 ms 700 KB Expected integer, but "failed" found
15 Halted 0 ms 0 KB -