Creating max heap and replacing top element if found a distance less then top element. What is the issue

#1

#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
priority_queue<pair<double,pair<int,int>>> pq;
vector<pair<int,int>> vec;
for(int i=0;i<n;i++){
int n1,n2;
cin>>n1>>n2;
vec.push_back(make_pair(n1,n2));
}
int k;
cin>>k;
for(int i=0;i<n;i++){
double dist = sqrt(vec[i].firstvec[i].first + vec[i].secondvec[i].second);
if(i<k){
pq.push(make_pair(dist,make_pair(vec[i].first,vec[i].second)));
}else{
pair<double,pair<int,int>> p = pq.top();
if(p.first>dist){
pq.pop();
pq.push(make_pair(dist,make_pair(vec[i].first,vec[i].second)));
}
}
}
while(pq.size()>0){
pair<double,pair<int,int>> p = pq.top();
cout<<p.second.first<<" "<<p.second.second<<endl;
pq.pop();
}

}

#2

code link https://ide.codingblocks.com/s/396090

#3

Hey @varss777

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    priority_queue<pair<int,pair<int,int>>> pq; //int instead of double
    vector<pair<int,int>> vec;
    for(int i=0;i<n;i++){
        int n1,n2;
        cin>>n1>>n2;
        vec.push_back(make_pair(n1,n2));
    }
    int k;
    cin>>k;
    for(int i=0;i<n;i++){
        int dist = (vec[i].first*vec[i].first + vec[i].second*vec[i].second);//int instead of double and removed sqrt
        if(i<k||pq.size()==0){ //updated 
            pq.push(make_pair(dist,make_pair(vec[i].first,vec[i].second)));
        }else{
            pair<int,pair<int,int>> p = pq.top(); //int  here
            if(p.first>dist){
                pq.pop();
                pq.push(make_pair(dist,make_pair(vec[i].first,vec[i].second)));
            }
        }        

    }
    vector<pair<int,int> > v;//added
    while(pq.size()>0){
        pair<int,pair<int,int>> p = pq.top(); //int
        // cout<<p.second.first<<" "<<p.second.second<<endl;not like this
        v.push_back({p.second.first,p.second.second});
        pq.pop();
    }
     sort(v.begin(),v.end());//added
    for(int i=0;i<v.size();i++){
        cout<<v[i].first<<" "<<v[i].second<<endl;
    } 
    return 0;

}
#4

thanks, i thought we have to print on the basis of distance i.e. “highest to lowest”

1 Like
#5

why this ? if(i<k||pq.size()==0)

#6

@varss777
u can remove pq.size()==0

#7

still giving me WA for one test case , after changing to int and sorting in vector.

#8

@varss777 your code seems fine, I also downloaded the testcase and code worked fine with it, seems some backend issue so don’t worry! Your code is fine.

#9

cool, thanks for confirmation. :slight_smile:

1 Like
#10

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.