답안 #886512

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
886512	2023-12-12T09:11:33 Z	vjudge1	함박 스테이크 (JOI20_hamburg)	C++17	15 / 100	231 ms	13520 KB

hamburg

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
const int inf = 1e9 + 10;

int n, k;
int l[N], r[N], u[N], d[N];

namespace brute {

vector<pair<int, int>> point;
int done[N];

void dfs(int step) {
        int minR = inf, maxL = -1, minU = inf, maxD = -1;
        for (int i = 0; i < n; i++) {
                if (done[i]) continue;
                minR = min(minR, r[i]);
                maxL = max(maxL, l[i]);
                minU = min(minU, u[i]);
                maxD = max(maxD, d[i]);
        }

        if (maxL == -1) {
                for (auto [x, y] : point) cout << x << ' ' << y << '\n';
                for (int i = point.size(); i < k; i++) cout << "1 1\n";
                exit(0);
        }

        if (step == k) return;

        for (int i = 0; i < 2; i++) {
                for (int j = 0; j < 2; j++) {
                        int x = i ? minR : maxL;
                        int y = j ? minU : maxD;
                        point.emplace_back(x, y);
                        vector<int> del;
                        for (int p = 0; p < n; p++) {
                                if (done[p]) continue;
                                if (l[p] <= x && x <= r[p] && d[p] <= y && y <= u[p]) {
                                        done[p] = 1;
                                        del.emplace_back(p);
                                }
                        }
                        dfs(step + 1);
                        for (int p : del) done[p] = 0;
                        point.pop_back();
                }
        }
}

};  // namespace brute

int32_t main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);

        cin >> n >> k;
        for (int i = 0; i < n; i++) cin >> l[i] >> d[i] >> r[i] >> u[i];

        brute::dfs(0);
}

Subtask #1
1.0 / 1.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	2604 KB	Output is correct
3	Correct	1 ms	2392 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct

Subtask #2
1.0 / 1.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2524 KB	Output is correct

Subtask #3
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2392 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2524 KB	Output is correct
8	Correct	3 ms	2652 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	2 ms	2396 KB	Output is correct
11	Correct	2 ms	2400 KB	Output is correct
12	Correct	2 ms	2600 KB	Output is correct

Subtask #4
0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	2616 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2528 KB	Output is correct
5	Correct	1 ms	2392 KB	Output is correct
6	Correct	1 ms	2604 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	7 ms	2644 KB	Output is correct
9	Correct	2 ms	2396 KB	Output is correct
10	Correct	5 ms	2608 KB	Output is correct
11	Correct	7 ms	2396 KB	Output is correct
12	Correct	4 ms	2396 KB	Output is correct
13	Correct	1 ms	2396 KB	Output is correct
14	Incorrect	7 ms	2396 KB	Unexpected end of file - int32 expected
15	Halted	0 ms	0 KB	-

Subtask #5
1.0 / 1.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	2604 KB	Output is correct
3	Correct	1 ms	2392 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	62 ms	13128 KB	Output is correct
6	Correct	62 ms	13248 KB	Output is correct
7	Correct	65 ms	13088 KB	Output is correct
8	Correct	61 ms	13156 KB	Output is correct

Subtask #6
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2524 KB	Output is correct
5	Correct	65 ms	13148 KB	Output is correct
6	Correct	77 ms	13520 KB	Output is correct
7	Correct	64 ms	13264 KB	Output is correct
8	Correct	76 ms	13304 KB	Output is correct

Subtask #7
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2392 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2524 KB	Output is correct
8	Correct	3 ms	2652 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	2 ms	2396 KB	Output is correct
11	Correct	2 ms	2400 KB	Output is correct
12	Correct	2 ms	2600 KB	Output is correct
13	Correct	72 ms	13264 KB	Output is correct
14	Correct	91 ms	13016 KB	Output is correct
15	Correct	69 ms	13160 KB	Output is correct
16	Correct	69 ms	13268 KB	Output is correct
17	Correct	67 ms	13172 KB	Output is correct
18	Correct	71 ms	13176 KB	Output is correct
19	Correct	74 ms	12944 KB	Output is correct
20	Correct	231 ms	13224 KB	Output is correct
21	Correct	92 ms	13052 KB	Output is correct
22	Correct	118 ms	13256 KB	Output is correct
23	Correct	166 ms	13356 KB	Output is correct
24	Correct	125 ms	13268 KB	Output is correct

Subtask #8
0 / 79.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	2616 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2528 KB	Output is correct
5	Correct	1 ms	2392 KB	Output is correct
6	Correct	1 ms	2604 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	7 ms	2644 KB	Output is correct
9	Correct	2 ms	2396 KB	Output is correct
10	Correct	5 ms	2608 KB	Output is correct
11	Correct	7 ms	2396 KB	Output is correct
12	Correct	4 ms	2396 KB	Output is correct
13	Correct	1 ms	2396 KB	Output is correct
14	Incorrect	7 ms	2396 KB	Unexpected end of file - int32 expected
15	Halted	0 ms	0 KB	-

답안 #886512

Compilation message