#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
int n,k,l[200001],d[200001],r[200001],u[200001];
vector <pair <int, int>> res;
vector <int> v;
bool solve(vector <int> v, int k){
if (v.empty()){
while (k--)
res.push_back({1,1});
return true;
}
if (!k)
return false;
int mn=INF,mx=0,mn2=INF,mx2=0;
for (int i:v){
mn=min(mn,r[i]);
mx=max(mx,l[i]);
mn2=min(mn2,u[i]);
mx2=max(mx2,d[i]);
}
vector <int> a,b;
a.push_back(mn);
b.push_back(mn2);
if (mn<mx)
a.push_back(mx);
if (mn2<mx2)
b.push_back(mx2);
if (a.size()==1||b.size()==1){
k-=a.size()*b.size();
for (int i:a)
for (int j:b)
res.push_back({i,j});
while (k--)
res.push_back({1,1});
return true;
}
if (k==1)
return false;
if (k==2){
for (int i=0;i<2;i++){
int ch=0;
for (int j:v)
ch+=((l[j]<=a[0]&&a[0]<=r[j]&&d[j]<=b[i]&&b[i]<=u[j])||(l[j]<=a[1]&&a[1]<=r[j]&&d[j]<=b[i^1]&&b[i^1]<=u[j]));
if (ch==v.size()){
res.push_back({a[0],b[i]});
res.push_back({a[1],b[i^1]});
return true;
}
}
return false;
}
if (k==3){
for (int i=0;i<2;i++)
for (int j=0;j<2;j++){
vector <int> v2;
for (int k:v)
if (l[k]>a[i]||r[k]<a[i]||d[k]>b[j]||u[k]<b[j])
v2.push_back(k);
if (solve(v2,k-1)){
res.push_back({a[i],b[j]});
return true;
}
}
return false;
}
return false;
}
int main(){
ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
cin >> n >> k;
for (int i=0;i<n;i++){
cin >> l[i] >> d[i] >> r[i] >> u[i];
v.push_back(i);
}
bool tmp=solve(v,k);
for (auto [x,y]:res)
cout << x << ' ' << y << '\n';
}
Compilation message
hamburg.cpp: In function 'bool solve(std::vector<int>, int)':
hamburg.cpp:45:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | if (ch==v.size()){
| ~~^~~~~~~~~~
hamburg.cpp: In function 'int main()':
hamburg.cpp:76:10: warning: unused variable 'tmp' [-Wunused-variable]
76 | bool tmp=solve(v,k);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2616 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 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 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2616 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2596 KB |
Output is correct |
| 5 |
Correct |
75 ms |
11212 KB |
Output is correct |
| 6 |
Correct |
62 ms |
11396 KB |
Output is correct |
| 7 |
Correct |
65 ms |
11220 KB |
Output is correct |
| 8 |
Correct |
74 ms |
11372 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 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 |
63 ms |
11380 KB |
Output is correct |
| 6 |
Correct |
70 ms |
11376 KB |
Output is correct |
| 7 |
Correct |
64 ms |
11356 KB |
Output is correct |
| 8 |
Correct |
76 ms |
11296 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
