Advertisement
Guest User

Untitled

a guest
Feb 20th, 2020
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.43 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include<queue>
  6. #include<string.h>
  7.  
  8. using namespace std;
  9. #define pb push_back
  10. #define mp make_pair
  11.  
  12.  
  13.  
  14.  
  15. int main()
  16. {
  17. int n,m;
  18. int l[100010],r[100010],tmp[100010];
  19. cin>>n>>m;
  20. // if( n>m ) swap( n,m );
  21. for( int i=0;i<n;i++ ) cin>>l[i];
  22. for(int i=0;i<m;i++) cin>>r[i];
  23. if( n>m ){
  24. for( int i=0;i<m;i++ ) tmp[i] = r[i];
  25. for( int i=0;i<n;i++ ) r[i]=l[i];
  26. for( int i=0;i<m;i++ ) l[i]=tmp[i];
  27. swap(n,m);
  28. }
  29. sort( l,l+n );
  30. sort( r,r+m );
  31. int lo=0,hi= 1000000000,mid,ans=1000000000;
  32. while(lo<=hi){
  33. mid=lo+(hi-lo)/2;
  34.  
  35. int curr=n-1;
  36. bool is=true;
  37. for( int i=m-1;i>=0;i-- ){
  38. if(curr<0) break;
  39. if( i < curr ){ ///ne mozemo ih sve uparit
  40. is=false;
  41. break;
  42. }
  43. // cout << i << " " << r[i] << " " << curr << " " << l[curr] << " eto " <<endl;
  44. if( abs( r[i] - l[curr] ) <= mid ){
  45. curr--;/// uparili smo curr pa sad uparujemo manji
  46. }
  47. }
  48. if( is && curr<0 ){ /// moze,probaj jos manju razliku
  49. hi=mid-1;
  50. ans=min(ans,mid);
  51. }
  52. else lo=mid+1;/// inace, probaj vecu razliku
  53. }
  54.  
  55. cout<<ans<<endl;
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement