#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define endl '\n'
#define pi pair<int, int>
#define f first
#define s second
struct rect{
int x, y, X, Y;
};
const int maxn = 200000;
int n, m, k;
int sz[4];
int cnt[maxn];
vector<rect> a;
vector<int> id;
vector<vector<int>> rin[4], rot[4];
int idx(int x){
return lower_bound(id.begin(), id.end(), x) - id.begin();
}
rect bnd(vector<rect> v){
rect ret = {m, m, 0, 0};
for(rect i : v){
ret.x = min(ret.x, i.X);
ret.y = min(ret.y, i.Y);
ret.X = max(ret.X, i.x);
ret.Y = max(ret.Y, i.y);
}
return ret;
}
bool crs(int a, int b, int c){
return a <= b && b <= c;
}
vector<pi> solve(vector<rect> v, int x){
rect f = bnd(v);
if(x == 1){
if(f.x < f.X || f.y < f.Y) return {};
else return {{f.x, f.y}};
}
vector<pi> pt = {{f.x, f.y}, {f.x, f.Y}, {f.X, f.y}, {f.X, f.Y}};
for(pi p : pt){
vector<rect> nv;
for(rect i : v){
if(!crs(i.x, p.f, i.X) || !crs(i.y, p.s, i.Y)) nv.push_back(i);
}
vector<pi> ret = solve(nv, x - 1);
if(!ret.empty()){
ret.push_back(p);
return ret;
}
}
return {};
}
int cur;
void add(int x){
if(!cnt[x]) cur++;
cnt[x]++;
}
void del(int x){
if(cnt[x] == 1) cur--;
cnt[x]--;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k;
a.resize(n);
for(int i = 0; i < n; i++){
cin >> a[i].x >> a[i].y >> a[i].X >> a[i].Y;
id.push_back(a[i].x);
id.push_back(a[i].y);
id.push_back(a[i].X);
id.push_back(a[i].Y);
}
sort(id.begin(), id.end());
id.erase(unique(id.begin(), id.end()), id.end());
m = id.size();
for(int i = 0; i < n; i++){
a[i].x = idx(a[i].x);
a[i].y = idx(a[i].y);
a[i].X = idx(a[i].X);
a[i].Y = idx(a[i].Y);
}
vector<pi> ans = solve(a, k);
if(!ans.empty()){
for(pi i : ans) cout << id[i.f] << " " << id[i.s] << endl;
return 0;
}
rect f = bnd(a);
sz[0] = sz[2] = f.X - f.x + 1, sz[1] = sz[3] = f.Y - f.y + 1;
for(int i = 0; i < 4; i++){
rin[i].resize(sz[i]);
rot[i].resize(sz[i]);
}
for(int i = 0; i < n; i++){
if(crs(a[i].y, f.y, a[i].Y)){
rin[0][max(0, a[i].x - f.x)].push_back(i);
rot[0][min(sz[0] - 1, a[i].X - f.x)].push_back(i);
}
if(crs(a[i].x, f.X, a[i].X)){
rin[1][max(0, a[i].y - f.y)].push_back(i);
rot[1][min(sz[1] - 1, a[i].Y - f.y)].push_back(i);
}
if(crs(a[i].y, f.Y, a[i].Y)){
rin[2][max(0, f.X - a[i].X)].push_back(i);
rot[2][min(sz[2] - 1, f.X - a[i].x)].push_back(i);
}
if(crs(a[i].x, f.x, a[i].X)){
rin[3][max(0, f.Y - a[i].Y)].push_back(i);
rot[3][min(sz[3] - 1, f.Y - a[i].y)].push_back(i);
}
}
for(int d = 0; d < 2; d++){
cur = 0;
for(int i = 0; i < n; i++) cnt[i] = 0;
for(int it[4] = {0, -1, -1, -1}, jt[4] = {0, 0, 0, 0}; it[0] < sz[0]; it[0]++){
for(int j : rin[0][it[0]]) add(j);
for(int t = 1; t < 4; t++){
while(it[t] < sz[t] - 1){
if(it[t] != -1){
bool w = 1;
for(; jt[t] < rot[t][it[t]].size(); jt[t]++){
if(cnt[rot[t][it[t]][jt[t]]] == 1){
w = 0;
break;
}
}
if(!w) break;
for(int j : rot[t][it[t]]) del(j);
}
it[t]++;
jt[t] = 0;
for(int j : rin[t][it[t]]) add(j);
}
}
if(cur == n){
if(d){
cout << id[f.X - it[0]] << " " << id[f.y] << endl;
cout << id[f.x] << " " << id[it[1] + f.y] << endl;
cout << id[it[2] + f.x] << " " << id[f.Y] << endl;
cout << id[f.X] << " " << id[f.Y - it[3]] << endl;
}else{
cout << id[it[0] + f.x] << " " << id[f.y] << endl;
cout << id[f.X] << " " << id[it[1] + f.y] << endl;
cout << id[f.X - it[2]] << " " << id[f.Y] << endl;
cout << id[f.x] << " " << id[f.Y - it[3]] << endl;
}
return 0;
}
for(int j : rot[0][it[0]]) del(j);
}
swap(rin[1], rin[3]), swap(rot[1], rot[3]);
for(int t = 0; t < 4; t++){
reverse(rin[t].begin(), rin[t].end());
reverse(rot[t].begin(), rot[t].end());
for(int i = 0; i < sz[t]; i++) swap(rin[t][i], rot[t][i]);
}
}
cout << -1 << endl;
return 0;
}
Compilation message
hamburg.cpp: In function 'int main()':
hamburg.cpp:140:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
140 | for(; jt[t] < rot[t][it[t]].size(); jt[t]++){
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
460 KB |
Output is correct |
2 |
Correct |
3 ms |
512 KB |
Output is correct |
3 |
Correct |
3 ms |
512 KB |
Output is correct |
4 |
Correct |
3 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
512 KB |
Output is correct |
2 |
Correct |
4 ms |
512 KB |
Output is correct |
3 |
Correct |
3 ms |
512 KB |
Output is correct |
4 |
Correct |
3 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
512 KB |
Output is correct |
2 |
Correct |
5 ms |
512 KB |
Output is correct |
3 |
Correct |
3 ms |
512 KB |
Output is correct |
4 |
Correct |
3 ms |
544 KB |
Output is correct |
5 |
Correct |
3 ms |
512 KB |
Output is correct |
6 |
Correct |
5 ms |
512 KB |
Output is correct |
7 |
Correct |
3 ms |
512 KB |
Output is correct |
8 |
Correct |
3 ms |
512 KB |
Output is correct |
9 |
Correct |
5 ms |
624 KB |
Output is correct |
10 |
Correct |
3 ms |
512 KB |
Output is correct |
11 |
Correct |
3 ms |
512 KB |
Output is correct |
12 |
Correct |
5 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
512 KB |
Output is correct |
2 |
Correct |
3 ms |
512 KB |
Output is correct |
3 |
Correct |
3 ms |
512 KB |
Output is correct |
4 |
Correct |
3 ms |
512 KB |
Output is correct |
5 |
Correct |
3 ms |
512 KB |
Output is correct |
6 |
Correct |
3 ms |
512 KB |
Output is correct |
7 |
Correct |
3 ms |
512 KB |
Output is correct |
8 |
Correct |
3 ms |
512 KB |
Output is correct |
9 |
Correct |
3 ms |
512 KB |
Output is correct |
10 |
Correct |
3 ms |
512 KB |
Output is correct |
11 |
Correct |
3 ms |
512 KB |
Output is correct |
12 |
Correct |
4 ms |
512 KB |
Output is correct |
13 |
Correct |
4 ms |
640 KB |
Output is correct |
14 |
Correct |
5 ms |
1076 KB |
Output is correct |
15 |
Correct |
4 ms |
640 KB |
Output is correct |
16 |
Correct |
4 ms |
640 KB |
Output is correct |
17 |
Correct |
5 ms |
1200 KB |
Output is correct |
18 |
Correct |
5 ms |
664 KB |
Output is correct |
19 |
Correct |
4 ms |
636 KB |
Output is correct |
20 |
Correct |
6 ms |
1316 KB |
Output is correct |
21 |
Correct |
5 ms |
640 KB |
Output is correct |
22 |
Correct |
5 ms |
688 KB |
Output is correct |
23 |
Correct |
6 ms |
1364 KB |
Output is correct |
24 |
Correct |
5 ms |
640 KB |
Output is correct |
25 |
Correct |
4 ms |
640 KB |
Output is correct |
26 |
Correct |
5 ms |
640 KB |
Output is correct |
27 |
Correct |
3 ms |
640 KB |
Output is correct |
28 |
Correct |
3 ms |
512 KB |
Output is correct |
29 |
Correct |
3 ms |
640 KB |
Output is correct |
30 |
Correct |
5 ms |
640 KB |
Output is correct |
31 |
Correct |
5 ms |
1084 KB |
Output is correct |
32 |
Correct |
6 ms |
992 KB |
Output is correct |
33 |
Correct |
6 ms |
1060 KB |
Output is correct |
34 |
Correct |
5 ms |
1016 KB |
Output is correct |
35 |
Correct |
6 ms |
1340 KB |
Output is correct |
36 |
Correct |
5 ms |
1088 KB |
Output is correct |
37 |
Correct |
6 ms |
1416 KB |
Output is correct |
38 |
Correct |
7 ms |
1480 KB |
Output is correct |
39 |
Correct |
5 ms |
1192 KB |
Output is correct |
40 |
Correct |
5 ms |
1136 KB |
Output is correct |
41 |
Correct |
5 ms |
1144 KB |
Output is correct |
42 |
Correct |
5 ms |
1292 KB |
Output is correct |
43 |
Correct |
5 ms |
1232 KB |
Output is correct |
44 |
Correct |
5 ms |
1236 KB |
Output is correct |
45 |
Correct |
4 ms |
640 KB |
Output is correct |
46 |
Correct |
5 ms |
1328 KB |
Output is correct |
47 |
Correct |
6 ms |
1200 KB |
Output is correct |
48 |
Correct |
6 ms |
1400 KB |
Output is correct |
49 |
Correct |
5 ms |
1236 KB |
Output is correct |
50 |
Correct |
6 ms |
1176 KB |
Output is correct |
51 |
Correct |
6 ms |
1392 KB |
Output is correct |
52 |
Correct |
5 ms |
1096 KB |
Output is correct |
53 |
Correct |
6 ms |
1216 KB |
Output is correct |
54 |
Correct |
6 ms |
1360 KB |
Output is correct |
55 |
Correct |
5 ms |
1256 KB |
Output is correct |
56 |
Correct |
5 ms |
1268 KB |
Output is correct |
57 |
Correct |
5 ms |
1156 KB |
Output is correct |
58 |
Correct |
5 ms |
1292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
460 KB |
Output is correct |
2 |
Correct |
3 ms |
512 KB |
Output is correct |
3 |
Correct |
3 ms |
512 KB |
Output is correct |
4 |
Correct |
3 ms |
512 KB |
Output is correct |
5 |
Correct |
341 ms |
12936 KB |
Output is correct |
6 |
Correct |
319 ms |
13028 KB |
Output is correct |
7 |
Correct |
324 ms |
13004 KB |
Output is correct |
8 |
Correct |
325 ms |
13072 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
512 KB |
Output is correct |
2 |
Correct |
4 ms |
512 KB |
Output is correct |
3 |
Correct |
3 ms |
512 KB |
Output is correct |
4 |
Correct |
3 ms |
512 KB |
Output is correct |
5 |
Correct |
343 ms |
14256 KB |
Output is correct |
6 |
Correct |
348 ms |
13912 KB |
Output is correct |
7 |
Correct |
351 ms |
14160 KB |
Output is correct |
8 |
Correct |
355 ms |
17124 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
512 KB |
Output is correct |
2 |
Correct |
5 ms |
512 KB |
Output is correct |
3 |
Correct |
3 ms |
512 KB |
Output is correct |
4 |
Correct |
3 ms |
544 KB |
Output is correct |
5 |
Correct |
3 ms |
512 KB |
Output is correct |
6 |
Correct |
5 ms |
512 KB |
Output is correct |
7 |
Correct |
3 ms |
512 KB |
Output is correct |
8 |
Correct |
3 ms |
512 KB |
Output is correct |
9 |
Correct |
5 ms |
624 KB |
Output is correct |
10 |
Correct |
3 ms |
512 KB |
Output is correct |
11 |
Correct |
3 ms |
512 KB |
Output is correct |
12 |
Correct |
5 ms |
512 KB |
Output is correct |
13 |
Correct |
346 ms |
14884 KB |
Output is correct |
14 |
Correct |
334 ms |
14636 KB |
Output is correct |
15 |
Correct |
332 ms |
12948 KB |
Output is correct |
16 |
Correct |
349 ms |
12932 KB |
Output is correct |
17 |
Correct |
364 ms |
16556 KB |
Output is correct |
18 |
Correct |
349 ms |
13028 KB |
Output is correct |
19 |
Correct |
340 ms |
16940 KB |
Output is correct |
20 |
Correct |
355 ms |
17712 KB |
Output is correct |
21 |
Correct |
428 ms |
26148 KB |
Output is correct |
22 |
Correct |
358 ms |
18440 KB |
Output is correct |
23 |
Correct |
354 ms |
21216 KB |
Output is correct |
24 |
Correct |
380 ms |
24276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
512 KB |
Output is correct |
2 |
Correct |
3 ms |
512 KB |
Output is correct |
3 |
Correct |
3 ms |
512 KB |
Output is correct |
4 |
Correct |
3 ms |
512 KB |
Output is correct |
5 |
Correct |
3 ms |
512 KB |
Output is correct |
6 |
Correct |
3 ms |
512 KB |
Output is correct |
7 |
Correct |
3 ms |
512 KB |
Output is correct |
8 |
Correct |
3 ms |
512 KB |
Output is correct |
9 |
Correct |
3 ms |
512 KB |
Output is correct |
10 |
Correct |
3 ms |
512 KB |
Output is correct |
11 |
Correct |
3 ms |
512 KB |
Output is correct |
12 |
Correct |
4 ms |
512 KB |
Output is correct |
13 |
Correct |
4 ms |
640 KB |
Output is correct |
14 |
Correct |
5 ms |
1076 KB |
Output is correct |
15 |
Correct |
4 ms |
640 KB |
Output is correct |
16 |
Correct |
4 ms |
640 KB |
Output is correct |
17 |
Correct |
5 ms |
1200 KB |
Output is correct |
18 |
Correct |
5 ms |
664 KB |
Output is correct |
19 |
Correct |
4 ms |
636 KB |
Output is correct |
20 |
Correct |
6 ms |
1316 KB |
Output is correct |
21 |
Correct |
5 ms |
640 KB |
Output is correct |
22 |
Correct |
5 ms |
688 KB |
Output is correct |
23 |
Correct |
6 ms |
1364 KB |
Output is correct |
24 |
Correct |
5 ms |
640 KB |
Output is correct |
25 |
Correct |
4 ms |
640 KB |
Output is correct |
26 |
Correct |
5 ms |
640 KB |
Output is correct |
27 |
Correct |
3 ms |
640 KB |
Output is correct |
28 |
Correct |
3 ms |
512 KB |
Output is correct |
29 |
Correct |
3 ms |
640 KB |
Output is correct |
30 |
Correct |
5 ms |
640 KB |
Output is correct |
31 |
Correct |
5 ms |
1084 KB |
Output is correct |
32 |
Correct |
6 ms |
992 KB |
Output is correct |
33 |
Correct |
6 ms |
1060 KB |
Output is correct |
34 |
Correct |
5 ms |
1016 KB |
Output is correct |
35 |
Correct |
6 ms |
1340 KB |
Output is correct |
36 |
Correct |
5 ms |
1088 KB |
Output is correct |
37 |
Correct |
6 ms |
1416 KB |
Output is correct |
38 |
Correct |
7 ms |
1480 KB |
Output is correct |
39 |
Correct |
5 ms |
1192 KB |
Output is correct |
40 |
Correct |
5 ms |
1136 KB |
Output is correct |
41 |
Correct |
5 ms |
1144 KB |
Output is correct |
42 |
Correct |
5 ms |
1292 KB |
Output is correct |
43 |
Correct |
5 ms |
1232 KB |
Output is correct |
44 |
Correct |
5 ms |
1236 KB |
Output is correct |
45 |
Correct |
4 ms |
640 KB |
Output is correct |
46 |
Correct |
5 ms |
1328 KB |
Output is correct |
47 |
Correct |
6 ms |
1200 KB |
Output is correct |
48 |
Correct |
6 ms |
1400 KB |
Output is correct |
49 |
Correct |
5 ms |
1236 KB |
Output is correct |
50 |
Correct |
6 ms |
1176 KB |
Output is correct |
51 |
Correct |
6 ms |
1392 KB |
Output is correct |
52 |
Correct |
5 ms |
1096 KB |
Output is correct |
53 |
Correct |
6 ms |
1216 KB |
Output is correct |
54 |
Correct |
6 ms |
1360 KB |
Output is correct |
55 |
Correct |
5 ms |
1256 KB |
Output is correct |
56 |
Correct |
5 ms |
1268 KB |
Output is correct |
57 |
Correct |
5 ms |
1156 KB |
Output is correct |
58 |
Correct |
5 ms |
1292 KB |
Output is correct |
59 |
Correct |
362 ms |
18144 KB |
Output is correct |
60 |
Correct |
346 ms |
16088 KB |
Output is correct |
61 |
Correct |
356 ms |
16476 KB |
Output is correct |
62 |
Correct |
356 ms |
15020 KB |
Output is correct |
63 |
Correct |
343 ms |
16472 KB |
Output is correct |
64 |
Correct |
349 ms |
13356 KB |
Output is correct |
65 |
Correct |
345 ms |
16812 KB |
Output is correct |
66 |
Correct |
346 ms |
15916 KB |
Output is correct |
67 |
Correct |
399 ms |
24296 KB |
Output is correct |
68 |
Correct |
375 ms |
22320 KB |
Output is correct |
69 |
Correct |
351 ms |
19020 KB |
Output is correct |
70 |
Correct |
388 ms |
23504 KB |
Output is correct |
71 |
Correct |
712 ms |
32440 KB |
Output is correct |
72 |
Correct |
982 ms |
96172 KB |
Output is correct |
73 |
Correct |
691 ms |
31676 KB |
Output is correct |
74 |
Correct |
568 ms |
32708 KB |
Output is correct |
75 |
Correct |
751 ms |
72860 KB |
Output is correct |
76 |
Correct |
499 ms |
30976 KB |
Output is correct |
77 |
Correct |
598 ms |
30736 KB |
Output is correct |
78 |
Correct |
1125 ms |
107340 KB |
Output is correct |
79 |
Correct |
571 ms |
32224 KB |
Output is correct |
80 |
Correct |
583 ms |
31188 KB |
Output is correct |
81 |
Correct |
1044 ms |
96384 KB |
Output is correct |
82 |
Correct |
510 ms |
27860 KB |
Output is correct |
83 |
Correct |
415 ms |
28892 KB |
Output is correct |
84 |
Correct |
408 ms |
23272 KB |
Output is correct |
85 |
Correct |
539 ms |
31568 KB |
Output is correct |
86 |
Correct |
439 ms |
25132 KB |
Output is correct |
87 |
Correct |
550 ms |
32272 KB |
Output is correct |
88 |
Correct |
491 ms |
31284 KB |
Output is correct |
89 |
Correct |
873 ms |
82188 KB |
Output is correct |
90 |
Correct |
1031 ms |
104308 KB |
Output is correct |
91 |
Correct |
860 ms |
79776 KB |
Output is correct |
92 |
Correct |
1198 ms |
111820 KB |
Output is correct |
93 |
Correct |
978 ms |
94716 KB |
Output is correct |
94 |
Correct |
1213 ms |
97676 KB |
Output is correct |
95 |
Correct |
1076 ms |
103328 KB |
Output is correct |
96 |
Correct |
896 ms |
89092 KB |
Output is correct |
97 |
Correct |
934 ms |
95788 KB |
Output is correct |
98 |
Correct |
945 ms |
94168 KB |
Output is correct |
99 |
Correct |
944 ms |
82736 KB |
Output is correct |
100 |
Correct |
1050 ms |
103840 KB |
Output is correct |
101 |
Correct |
1060 ms |
100944 KB |
Output is correct |
102 |
Correct |
738 ms |
67304 KB |
Output is correct |
103 |
Correct |
1137 ms |
110068 KB |
Output is correct |
104 |
Correct |
868 ms |
77884 KB |
Output is correct |
105 |
Correct |
1065 ms |
109176 KB |
Output is correct |
106 |
Correct |
1004 ms |
102196 KB |
Output is correct |
107 |
Correct |
984 ms |
92652 KB |
Output is correct |
108 |
Correct |
1099 ms |
104496 KB |
Output is correct |
109 |
Correct |
1111 ms |
105744 KB |
Output is correct |
110 |
Correct |
1012 ms |
99820 KB |
Output is correct |
111 |
Correct |
878 ms |
92192 KB |
Output is correct |
112 |
Correct |
1151 ms |
107760 KB |
Output is correct |
113 |
Correct |
792 ms |
90152 KB |
Output is correct |
114 |
Correct |
791 ms |
90148 KB |
Output is correct |
115 |
Correct |
775 ms |
90180 KB |
Output is correct |
116 |
Correct |
786 ms |
90084 KB |
Output is correct |
117 |
Correct |
622 ms |
31084 KB |
Output is correct |
118 |
Correct |
655 ms |
31016 KB |
Output is correct |
119 |
Correct |
631 ms |
31060 KB |
Output is correct |
120 |
Correct |
613 ms |
31064 KB |
Output is correct |
121 |
Correct |
631 ms |
30984 KB |
Output is correct |
122 |
Correct |
656 ms |
31128 KB |
Output is correct |
123 |
Correct |
619 ms |
31064 KB |
Output is correct |
124 |
Correct |
623 ms |
31028 KB |
Output is correct |
125 |
Correct |
636 ms |
31332 KB |
Output is correct |
126 |
Correct |
648 ms |
31036 KB |
Output is correct |