#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
const int maxn = 2e5 + 10;
const int inf = 1e9 + 1;
int L[maxn], R[maxn], D[maxn], U[maxn];
int mark[maxn];
pair<int,int> ans[5];
int rot = 0;
inline bool check(int,int,int,int);
bool solve(int n, int k){
if (k == 1){
bool cor = 1;
int x = inf-1, y = inf-1;
for (int i = 1; i <= n; i++)
if (!mark[i])
x = min(x, R[i]), y = min(y, U[i]);
for (int i = 1; i <= n; i++)
if (!mark[i])
cor &= (L[i] <= x and x <= R[i] and D[i] <= y and y <= U[i]);
if (cor)
ans[k] = {x,y};
return cor;
}
if (k == 2){
int x = inf-1, y1 = inf-1, y2 = 1;
for (int i = 1; i <= n; i++)
if (!mark[i])
x = min(x, R[i]), y1 = min(y1, U[i]), y2 = max(y2, D[i]);
bool ret = check(n, k, x, y1);
if (ret == true)
return true;
ret = check(n, k, x, y2);
return ret;
}
if (k == 3){
int x1 = inf-1, x2 = 1, y1 = inf-1, y2 = 1;
for (int i = 1; i <= n; i++)
if (!mark[i])
x1 = min(x1, R[i]), x2 = max(x2, L[i]), y1 = min(y1, U[i]), y2 = max(y2, D[i]);
bool ret = check(n, k, x1, y1);
if (ret == true)
return true;
ret = check(n, k, x1, y2);
if (ret == true)
return true;
ret = check(n, k, x2, y1);
if (ret == true)
return true;
ret = check(n, k, x2, y2);
return ret;
}
if (k == 4){
int x = inf-1;
for (int i = 1; i <= n; i++)
x = min(x, R[i]);
vector<pair<int,int>> seg;
for (int i = 1; i <= n; i++)
if (L[i] <= x)
seg.push_back({D[i],i});
sort(seg.rbegin(), seg.rend());
int minl = inf;
for (auto it : seg){
int idx = it.second;
if (U[idx] < minl){
bool ret = check(n, k, x, U[idx]);
if (ret)
return true;
minl = U[idx];
}
}
int cnt = 0;
for (int i = 1; i <= n; i++)
if (L[i] <= x)
seg[cnt++] = {U[i],i};
sort(seg.begin(), seg.end());
int maxr = 0;
for (auto it : seg){
int idx = it.second;
if (maxr < D[idx]){
bool ret = check(n, k, x, D[idx]);
if (ret)
return true;
maxr = D[idx];
}
}
if (rot == 0){
for (int i = 1; i <= n; i++){
int l = L[i], r = R[i], u = U[i], d = D[i];
L[i] = inf - r, R[i] = inf - l;
}
rot ++;
bool ret = solve(n,k);
if (ret == true){
for (int i = 1; i <= k; i++)
ans[i].first = inf - ans[i].first;
return true;
}
}
}
return false;
}
inline bool check(int n, int k, int x, int y){
for (int i = 1; i <= n; i++)
if (!mark[i] and L[i] <= x and x <= R[i] and D[i] <= y and y <= U[i])
mark[i] = k;
ans[k] = {x,y};
bool ret = solve(n, k-1);
if (ret == true)
return true;
for (int i = 1; i <= n; i++)
if (mark[i] == k)
mark[i] = 0;
return false;
}
int main(){
ios_base::sync_with_stdio(false);
int n, k;
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++)
scanf("%d%d%d%d", &L[i], &D[i], &R[i], &U[i]);
bool solved = solve(n, k);
assert(solved);
for (int i = 1; i <= k; i++)
printf("%d %d\n", ans[i].first, ans[i].second);
}
Compilation message
hamburg.cpp: In function 'bool solve(int, int)':
hamburg.cpp:94:29: warning: unused variable 'u' [-Wunused-variable]
94 | int l = L[i], r = R[i], u = U[i], d = D[i];
| ^
hamburg.cpp:94:39: warning: unused variable 'd' [-Wunused-variable]
94 | int l = L[i], r = R[i], u = U[i], d = D[i];
| ^
hamburg.cpp: In function 'int main()':
hamburg.cpp:126:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
126 | scanf("%d%d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~
hamburg.cpp:128:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
128 | scanf("%d%d%d%d", &L[i], &D[i], &R[i], &U[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
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 |
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 |
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 |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
3 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 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
3 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 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 |
5 ms |
496 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
3 ms |
384 KB |
Output is correct |
7 |
Correct |
10 ms |
384 KB |
Output is correct |
8 |
Correct |
8 ms |
384 KB |
Output is correct |
9 |
Correct |
7 ms |
384 KB |
Output is correct |
10 |
Correct |
7 ms |
384 KB |
Output is correct |
11 |
Correct |
10 ms |
488 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
9 ms |
384 KB |
Output is correct |
14 |
Correct |
10 ms |
384 KB |
Output is correct |
15 |
Correct |
7 ms |
384 KB |
Output is correct |
16 |
Correct |
12 ms |
384 KB |
Output is correct |
17 |
Correct |
8 ms |
384 KB |
Output is correct |
18 |
Correct |
7 ms |
384 KB |
Output is correct |
19 |
Correct |
8 ms |
384 KB |
Output is correct |
20 |
Correct |
6 ms |
384 KB |
Output is correct |
21 |
Correct |
11 ms |
384 KB |
Output is correct |
22 |
Correct |
8 ms |
384 KB |
Output is correct |
23 |
Correct |
8 ms |
384 KB |
Output is correct |
24 |
Correct |
13 ms |
384 KB |
Output is correct |
25 |
Correct |
5 ms |
384 KB |
Output is correct |
26 |
Correct |
5 ms |
416 KB |
Output is correct |
27 |
Correct |
4 ms |
384 KB |
Output is correct |
28 |
Correct |
14 ms |
384 KB |
Output is correct |
29 |
Correct |
16 ms |
384 KB |
Output is correct |
30 |
Correct |
3 ms |
384 KB |
Output is correct |
31 |
Correct |
7 ms |
384 KB |
Output is correct |
32 |
Correct |
6 ms |
384 KB |
Output is correct |
33 |
Correct |
10 ms |
384 KB |
Output is correct |
34 |
Correct |
8 ms |
384 KB |
Output is correct |
35 |
Correct |
6 ms |
384 KB |
Output is correct |
36 |
Correct |
8 ms |
384 KB |
Output is correct |
37 |
Correct |
27 ms |
488 KB |
Output is correct |
38 |
Correct |
7 ms |
384 KB |
Output is correct |
39 |
Correct |
20 ms |
480 KB |
Output is correct |
40 |
Correct |
8 ms |
384 KB |
Output is correct |
41 |
Correct |
7 ms |
488 KB |
Output is correct |
42 |
Correct |
10 ms |
384 KB |
Output is correct |
43 |
Correct |
14 ms |
488 KB |
Output is correct |
44 |
Correct |
4 ms |
384 KB |
Output is correct |
45 |
Correct |
4 ms |
384 KB |
Output is correct |
46 |
Correct |
9 ms |
512 KB |
Output is correct |
47 |
Correct |
7 ms |
384 KB |
Output is correct |
48 |
Correct |
6 ms |
384 KB |
Output is correct |
49 |
Correct |
9 ms |
384 KB |
Output is correct |
50 |
Correct |
6 ms |
484 KB |
Output is correct |
51 |
Correct |
10 ms |
480 KB |
Output is correct |
52 |
Correct |
5 ms |
436 KB |
Output is correct |
53 |
Correct |
4 ms |
384 KB |
Output is correct |
54 |
Correct |
7 ms |
384 KB |
Output is correct |
55 |
Correct |
10 ms |
384 KB |
Output is correct |
56 |
Correct |
10 ms |
384 KB |
Output is correct |
57 |
Correct |
14 ms |
384 KB |
Output is correct |
58 |
Correct |
12 ms |
384 KB |
Output is correct |
# |
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 |
142 ms |
3448 KB |
Output is correct |
6 |
Correct |
143 ms |
3448 KB |
Output is correct |
7 |
Correct |
139 ms |
3460 KB |
Output is correct |
8 |
Correct |
136 ms |
3480 KB |
Output is correct |
# |
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 |
3 ms |
384 KB |
Output is correct |
5 |
Correct |
140 ms |
4216 KB |
Output is correct |
6 |
Correct |
142 ms |
4216 KB |
Output is correct |
7 |
Correct |
144 ms |
4300 KB |
Output is correct |
8 |
Correct |
149 ms |
4216 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 |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
3 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 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
3 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
151 ms |
4252 KB |
Output is correct |
14 |
Correct |
158 ms |
4216 KB |
Output is correct |
15 |
Correct |
147 ms |
4204 KB |
Output is correct |
16 |
Correct |
147 ms |
4288 KB |
Output is correct |
17 |
Correct |
161 ms |
4216 KB |
Output is correct |
18 |
Correct |
145 ms |
4304 KB |
Output is correct |
19 |
Correct |
188 ms |
4220 KB |
Output is correct |
20 |
Correct |
150 ms |
4232 KB |
Output is correct |
21 |
Correct |
195 ms |
4276 KB |
Output is correct |
22 |
Correct |
166 ms |
4200 KB |
Output is correct |
23 |
Correct |
225 ms |
4216 KB |
Output is correct |
24 |
Correct |
205 ms |
4276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 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 |
5 ms |
496 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
3 ms |
384 KB |
Output is correct |
7 |
Correct |
10 ms |
384 KB |
Output is correct |
8 |
Correct |
8 ms |
384 KB |
Output is correct |
9 |
Correct |
7 ms |
384 KB |
Output is correct |
10 |
Correct |
7 ms |
384 KB |
Output is correct |
11 |
Correct |
10 ms |
488 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
9 ms |
384 KB |
Output is correct |
14 |
Correct |
10 ms |
384 KB |
Output is correct |
15 |
Correct |
7 ms |
384 KB |
Output is correct |
16 |
Correct |
12 ms |
384 KB |
Output is correct |
17 |
Correct |
8 ms |
384 KB |
Output is correct |
18 |
Correct |
7 ms |
384 KB |
Output is correct |
19 |
Correct |
8 ms |
384 KB |
Output is correct |
20 |
Correct |
6 ms |
384 KB |
Output is correct |
21 |
Correct |
11 ms |
384 KB |
Output is correct |
22 |
Correct |
8 ms |
384 KB |
Output is correct |
23 |
Correct |
8 ms |
384 KB |
Output is correct |
24 |
Correct |
13 ms |
384 KB |
Output is correct |
25 |
Correct |
5 ms |
384 KB |
Output is correct |
26 |
Correct |
5 ms |
416 KB |
Output is correct |
27 |
Correct |
4 ms |
384 KB |
Output is correct |
28 |
Correct |
14 ms |
384 KB |
Output is correct |
29 |
Correct |
16 ms |
384 KB |
Output is correct |
30 |
Correct |
3 ms |
384 KB |
Output is correct |
31 |
Correct |
7 ms |
384 KB |
Output is correct |
32 |
Correct |
6 ms |
384 KB |
Output is correct |
33 |
Correct |
10 ms |
384 KB |
Output is correct |
34 |
Correct |
8 ms |
384 KB |
Output is correct |
35 |
Correct |
6 ms |
384 KB |
Output is correct |
36 |
Correct |
8 ms |
384 KB |
Output is correct |
37 |
Correct |
27 ms |
488 KB |
Output is correct |
38 |
Correct |
7 ms |
384 KB |
Output is correct |
39 |
Correct |
20 ms |
480 KB |
Output is correct |
40 |
Correct |
8 ms |
384 KB |
Output is correct |
41 |
Correct |
7 ms |
488 KB |
Output is correct |
42 |
Correct |
10 ms |
384 KB |
Output is correct |
43 |
Correct |
14 ms |
488 KB |
Output is correct |
44 |
Correct |
4 ms |
384 KB |
Output is correct |
45 |
Correct |
4 ms |
384 KB |
Output is correct |
46 |
Correct |
9 ms |
512 KB |
Output is correct |
47 |
Correct |
7 ms |
384 KB |
Output is correct |
48 |
Correct |
6 ms |
384 KB |
Output is correct |
49 |
Correct |
9 ms |
384 KB |
Output is correct |
50 |
Correct |
6 ms |
484 KB |
Output is correct |
51 |
Correct |
10 ms |
480 KB |
Output is correct |
52 |
Correct |
5 ms |
436 KB |
Output is correct |
53 |
Correct |
4 ms |
384 KB |
Output is correct |
54 |
Correct |
7 ms |
384 KB |
Output is correct |
55 |
Correct |
10 ms |
384 KB |
Output is correct |
56 |
Correct |
10 ms |
384 KB |
Output is correct |
57 |
Correct |
14 ms |
384 KB |
Output is correct |
58 |
Correct |
12 ms |
384 KB |
Output is correct |
59 |
Correct |
641 ms |
4960 KB |
Output is correct |
60 |
Correct |
618 ms |
5920 KB |
Output is correct |
61 |
Correct |
448 ms |
5360 KB |
Output is correct |
62 |
Correct |
479 ms |
5896 KB |
Output is correct |
63 |
Correct |
531 ms |
4988 KB |
Output is correct |
64 |
Correct |
401 ms |
6024 KB |
Output is correct |
65 |
Correct |
2009 ms |
5212 KB |
Output is correct |
66 |
Correct |
1954 ms |
5616 KB |
Output is correct |
67 |
Correct |
1312 ms |
4724 KB |
Output is correct |
68 |
Correct |
2930 ms |
5232 KB |
Output is correct |
69 |
Correct |
2436 ms |
5360 KB |
Output is correct |
70 |
Correct |
1002 ms |
4976 KB |
Output is correct |
71 |
Correct |
1332 ms |
5232 KB |
Output is correct |
72 |
Correct |
1373 ms |
5108 KB |
Output is correct |
73 |
Correct |
1141 ms |
4976 KB |
Output is correct |
74 |
Correct |
2557 ms |
4976 KB |
Output is correct |
75 |
Correct |
1151 ms |
5616 KB |
Output is correct |
76 |
Correct |
2937 ms |
5648 KB |
Output is correct |
77 |
Correct |
877 ms |
5260 KB |
Output is correct |
78 |
Execution timed out |
3044 ms |
5992 KB |
Time limit exceeded |
79 |
Halted |
0 ms |
0 KB |
- |