Having some problems in CSES "Apartment" problem

help
1

I’ve tried to solve this question using binary search but I guess I got a wrong answer due to duplicates elements in a[i]. I need to optimize my code a bit but I don’t know how can anyone help me here.
problem Link: CSES - Apartments

2

I don’t think you need binary search for this problem rather a trivial two pointer on the sorted arrays will also do the job. There’s not much to explain unless you know two pointers. I’ve attached the AC code below.

AC_CODE 
#include<bits/stdc++.h>
using namespace std ;
int main(){
  int n,m,k,ans=0;
  cin >> n >> m >> k ;
  vector<int>a(n),b(m) ;
  for(int &x:a)
    cin >> x  ;
  for(int &x:b)
    cin >> x ;
  sort(a.begin(),a.end()) ;
  sort(b.begin(),b.end()) ;
  for(int i=0,j=0;i<n;i++){
    while(j<m&&b[j]<a[i]-k)
      ++j ;
    if(j<m&&b[j]<=a[i]+k)
      ++ans,++j ;
  }
  cout << ans  ;
}
1 Like