#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
const int MAXK = 4;
const int INF = 1000000000;
struct Drept {
int x1, y1, x2, y2;
} v[MAXN], sol[MAXK + 5];
pair<bool, Drept> inters(const Drept& a, const Drept& b) {
Drept c;
c.x1 = max(a.x1, b.x1);
c.y1 = max(a.y1, b.y1);
c.x2 = min(a.x2, b.x2);
c.y2 = min(a.y2, b.y2);
if (c.x1 <= c.x2 && c.y1 <= c.y2)
return {1, c};
return {0, c};
}
int main() {
//freopen("date.in", "r", stdin);
//freopen("date.out", "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, k;
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; ++i)
scanf("%d%d%d%d", &v[i].x1, &v[i].y1, &v[i].x2, &v[i].y2);
while (1) {
for (int i = 1; i <= k; ++i)
sol[i] = {1, 1, INF, INF};
shuffle(v + 1, v + n + 1, rng);
bool gas = 1;
for (int i = 1; i <= n; ++i) {
bool ok = 0;
for (int j = 1; j <= k; ++j) {
pair<bool, Drept>aux = inters(sol[j], v[i]);
if (aux.first) {
sol[j] = aux.second;
ok = 1;
break;
}
}
if (!ok) {
gas = 0;
break;
}
}
if (gas) {
for (int i = 1; i <= k; ++i)
printf("%d %d\n", sol[i].x1, sol[i].y1);
return 0;
}
}
return 0;
}
Compilation message
hamburg.cpp: In function 'int main()':
hamburg.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
30 | scanf("%d%d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~
hamburg.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
32 | scanf("%d%d%d%d", &v[i].x1, &v[i].y1, &v[i].x2, &v[i].y2);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
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 |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
3 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
59 ms |
400 KB |
Output is correct |
9 |
Correct |
3 ms |
384 KB |
Output is correct |
10 |
Correct |
95 ms |
384 KB |
Output is correct |
11 |
Correct |
3 ms |
384 KB |
Output is correct |
12 |
Correct |
3 ms |
384 KB |
Output is correct |
# |
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 |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
3 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
3 ms |
384 KB |
Output is correct |
7 |
Correct |
72 ms |
400 KB |
Output is correct |
8 |
Correct |
24 ms |
384 KB |
Output is correct |
9 |
Correct |
24 ms |
384 KB |
Output is correct |
10 |
Correct |
276 ms |
504 KB |
Output is correct |
11 |
Correct |
432 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
837 ms |
400 KB |
Output is correct |
14 |
Correct |
201 ms |
384 KB |
Output is correct |
15 |
Correct |
213 ms |
384 KB |
Output is correct |
16 |
Correct |
219 ms |
400 KB |
Output is correct |
17 |
Correct |
78 ms |
504 KB |
Output is correct |
18 |
Correct |
791 ms |
504 KB |
Output is correct |
19 |
Correct |
149 ms |
384 KB |
Output is correct |
20 |
Execution timed out |
3039 ms |
384 KB |
Time limit exceeded |
21 |
Halted |
0 ms |
0 KB |
- |
# |
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 |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
154 ms |
3420 KB |
Output is correct |
6 |
Correct |
145 ms |
3448 KB |
Output is correct |
7 |
Correct |
150 ms |
3496 KB |
Output is correct |
8 |
Correct |
153 ms |
3448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 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 |
992 ms |
3704 KB |
Output is correct |
6 |
Execution timed out |
3079 ms |
3448 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
3 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
59 ms |
400 KB |
Output is correct |
9 |
Correct |
3 ms |
384 KB |
Output is correct |
10 |
Correct |
95 ms |
384 KB |
Output is correct |
11 |
Correct |
3 ms |
384 KB |
Output is correct |
12 |
Correct |
3 ms |
384 KB |
Output is correct |
13 |
Correct |
1695 ms |
3496 KB |
Output is correct |
14 |
Correct |
370 ms |
3452 KB |
Output is correct |
15 |
Correct |
841 ms |
3576 KB |
Output is correct |
16 |
Execution timed out |
3099 ms |
3448 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |
# |
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 |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
3 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
3 ms |
384 KB |
Output is correct |
7 |
Correct |
72 ms |
400 KB |
Output is correct |
8 |
Correct |
24 ms |
384 KB |
Output is correct |
9 |
Correct |
24 ms |
384 KB |
Output is correct |
10 |
Correct |
276 ms |
504 KB |
Output is correct |
11 |
Correct |
432 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
837 ms |
400 KB |
Output is correct |
14 |
Correct |
201 ms |
384 KB |
Output is correct |
15 |
Correct |
213 ms |
384 KB |
Output is correct |
16 |
Correct |
219 ms |
400 KB |
Output is correct |
17 |
Correct |
78 ms |
504 KB |
Output is correct |
18 |
Correct |
791 ms |
504 KB |
Output is correct |
19 |
Correct |
149 ms |
384 KB |
Output is correct |
20 |
Execution timed out |
3039 ms |
384 KB |
Time limit exceeded |
21 |
Halted |
0 ms |
0 KB |
- |