# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
1049924 |
2024-08-09T06:09:35 Z |
아침연습다풀고 hamburg 풀면 복붙날먹치팅할거임(#11102) |
함박 스테이크 (JOI20_hamburg) |
C++17 |
|
154 ms |
37644 KB |
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<lint, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define cr(v, n) (v).clear(), (v).resize(n);
struct rect {
int sx, sy, ex, ey;
};
vector<pi> trace;
vector<rect> chop(vector<rect> a, pi p) {
vector<rect> z;
for (auto &r : a) {
if (r.sx <= p[0] && p[0] <= r.ex && r.sy <= p[1] && p[1] <= r.ey)
continue;
z.push_back(r);
}
return z;
}
void backtrack(vector<rect> a, int k, int p) {
if (sz(a) == 0) {
for (int i = 0; i < p; i++) {
cout << trace[i % sz(trace)][0] << " " << trace[i % sz(trace)][1] << "\n";
}
exit(0);
}
if (k == 0)
return;
int xmin = 2e9, ymin = 2e9, xmax = -2e9, ymax = -2e9;
for (auto &x : a) {
xmin = min(xmin, x.ex);
ymin = min(ymin, x.ey);
xmax = max(xmax, x.sx);
ymax = max(ymax, x.sy);
}
vector<pi> cp = {pi{xmax, ymax}, pi{xmax, ymin}, pi{xmin, ymax}, pi{xmin, ymin}};
for (auto &v : cp) {
trace.push_back(v);
backtrack(chop(a, v), k - 1, p);
trace.pop_back();
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, k;
cin >> n >> k;
vector<rect> a(n);
int xmin = 2e9, ymin = 2e9, xmax = -2e9, ymax = -2e9;
for (auto &x : a) {
cin >> x.sx >> x.sy >> x.ex >> x.ey;
xmin = min(xmin, x.ex);
ymin = min(ymin, x.ey);
xmax = max(xmax, x.sx);
ymax = max(ymax, x.sy);
}
backtrack(a, k, k);
assert(xmin < xmax && ymin < ymax);
vector<rect> w;
int is = ymin + 1, ie = ymax - 1;
for (auto &v : a) {
if (v.sx <= xmin && xmax <= v.ex) {
if (v.sy <= ymin && ymin <= v.ey)
continue;
if (v.sy <= ymax && ymax <= v.ey)
continue;
// two cross |
w.push_back(v);
}
if (v.sy <= ymin && ymax <= v.ey) {
if (v.sx <= xmin && xmin <= v.ex)
continue;
if (v.sx <= xmax && xmax <= v.ex)
continue;
// two cross -
w.push_back(v);
}
if (v.ex < xmax && v.sy > ymin && v.ey < ymax) {
is = max(is, v.sy);
ie = min(ie, v.ey);
}
}
a = w;
for (auto &v : a) {
if (v.ey >= is && v.ey <= ie) {
trace.push_back({xmin, v.ey});
backtrack(chop(a, trace[0]), k - 1, k);
trace.pop_back();
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
600 KB |
Output is correct |
3 |
Correct |
1 ms |
564 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
604 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
2 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
2 ms |
600 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
560 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
2 ms |
860 KB |
Output is correct |
9 |
Correct |
2 ms |
604 KB |
Output is correct |
10 |
Correct |
2 ms |
604 KB |
Output is correct |
11 |
Correct |
3 ms |
756 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
14 |
Incorrect |
2 ms |
844 KB |
Unexpected end of file - int32 expected |
15 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
55 ms |
17616 KB |
Output is correct |
6 |
Correct |
49 ms |
17492 KB |
Output is correct |
7 |
Correct |
47 ms |
17488 KB |
Output is correct |
8 |
Correct |
46 ms |
17400 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
600 KB |
Output is correct |
3 |
Correct |
1 ms |
564 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
53 ms |
20680 KB |
Output is correct |
6 |
Correct |
56 ms |
24012 KB |
Output is correct |
7 |
Correct |
49 ms |
20424 KB |
Output is correct |
8 |
Correct |
61 ms |
31468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
604 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
2 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
2 ms |
600 KB |
Output is correct |
13 |
Correct |
50 ms |
22488 KB |
Output is correct |
14 |
Correct |
49 ms |
22368 KB |
Output is correct |
15 |
Correct |
50 ms |
22988 KB |
Output is correct |
16 |
Correct |
48 ms |
20444 KB |
Output is correct |
17 |
Correct |
49 ms |
21704 KB |
Output is correct |
18 |
Correct |
55 ms |
19812 KB |
Output is correct |
19 |
Correct |
49 ms |
24008 KB |
Output is correct |
20 |
Correct |
154 ms |
37644 KB |
Output is correct |
21 |
Correct |
61 ms |
26308 KB |
Output is correct |
22 |
Correct |
83 ms |
36688 KB |
Output is correct |
23 |
Correct |
109 ms |
36048 KB |
Output is correct |
24 |
Correct |
93 ms |
34976 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
560 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
2 ms |
860 KB |
Output is correct |
9 |
Correct |
2 ms |
604 KB |
Output is correct |
10 |
Correct |
2 ms |
604 KB |
Output is correct |
11 |
Correct |
3 ms |
756 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
14 |
Incorrect |
2 ms |
844 KB |
Unexpected end of file - int32 expected |
15 |
Halted |
0 ms |
0 KB |
- |