#include <bits/stdc++.h>
using namespace std;
struct pont{
int x,y;
int s;
};
struct par{
int a,b;
};
struct classcomp1{
bool operator() (pont x,pont y) {
return((x.x<y.x)||((x.x==y.x)&&(x.s<y.s)));
}
};
struct classcomp2{
bool operator() (pont x,pont y) {
return((x.y<y.y)||((x.y==y.y)&&(x.s<y.s)));
}
};
bool kis(pont x,pont y) {
return((x.y<y.y)||((x.y==y.y)&&(x.x<y.x)));
};
int n,k;
int x,y;
vector<pont> t;
vector<pont> orig;
vector<pont> t2;
pont z;
vector<par> cur,ma;
par q;
set<pont,classcomp1> s1;
set<pont,classcomp1>::iterator it1;
set<pont,classcomp2> s2;
set<pont,classcomp2>::iterator it2;
bool exist(int d) {
cur.clear(); s1.clear(); s2.clear();
for (pont i:t2) {
//cout << d << " " << i.s << endl;
while ((s2.size()>0)&&((*s2.begin()).y<i.y-d)) {
//cout << d << " " << i.s << " erase: " << (*s2.begin()).s << endl;
s1.erase((*s2.begin()));
s2.erase(s2.begin());
}
z=i; z.x-=d; z.s=-1;
for (it1=s1.lower_bound(z);(it1!=s1.end())&&((*it1).x<=i.x+d);it1++) {
//cout << d << " " << i.s << " found: " << (*it1).s << endl;
q.a=i.s; q.b=(*it1).s;
cur.push_back(q);
if (cur.size()>=k) {
//cout << d << " true" << endl;
return(true);
}
}
s1.insert(i);
s2.insert(i);
}
//cout << d << " false" << endl;
return(false);
}
int log_search(int l,int r) {
//cout << l << " " << r << endl;
if (l==r) {
return(l);
}
if (exist((l+r)/2+1)) {
ma=cur;
return(log_search(l,(l+r)/2));
} else {
return(log_search((l+r)/2+1,r));
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k;
for (int i=0;i<n;i++) {
cin >> x >> y;
z.x=x+y; z.y=x-y; z.s=i;
t.push_back(z);
z.x=x; z.y=y; z.s=i;
orig.push_back(z);
}
t2=t;
sort(t2.begin(),t2.end(),kis);
int ans=log_search(1,2e9);
exist(ans);
vector<int> lengths; lengths.clear();
for (par i:cur) {
lengths.push_back(abs(orig[i.a].x-orig[i.b].x)+abs(orig[i.a].y-orig[i.b].y));
}
//cout << lengths.size() << endl;
for (;lengths.size()<k;) {
lengths.push_back(ans+1);
}
sort(lengths.begin(),lengths.end());
for (int i:lengths) {
cout << i << endl;
}
return 0;
}
/*
3 2
-1 0
0 2
0 0
*/
/*
5 4
1 -1
2 0
-1 0
0 2
0 -2
*/
Compilation message
road_construction.cpp: In function 'bool exist(int)':
road_construction.cpp:57:27: warning: comparison of integer expressions of different signedness: 'std::vector<par>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
57 | if (cur.size()>=k) {
| ~~~~~~~~~~^~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:103:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
103 | for (;lengths.size()<k;) {
| ~~~~~~~~~~~~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10011 ms |
2580 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
850 ms |
17676 KB |
Output is correct |
| 2 |
Correct |
830 ms |
19376 KB |
Output is correct |
| 3 |
Execution timed out |
10049 ms |
2504 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
276 ms |
9648 KB |
Output is correct |
| 2 |
Correct |
438 ms |
14380 KB |
Output is correct |
| 3 |
Execution timed out |
10021 ms |
212 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
276 ms |
9648 KB |
Output is correct |
| 2 |
Correct |
438 ms |
14380 KB |
Output is correct |
| 3 |
Execution timed out |
10021 ms |
212 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10011 ms |
2580 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10011 ms |
2580 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
