fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int Mod=998244353;
  5.  
  6.  bool f(int mid, vector<int> &a , vector<int> &b){
  7.   int cnt=0;
  8.   for(int i=0;i<a.size();i++){
  9.   	if(cnt==0){
  10.     if(a[i]>b[cnt]+mid && a[i]<b[cnt]-mid) return false;
  11.      cnt++;
  12.   }
  13.    else{
  14.    	if(a[i]>b[cnt-1]+mid && a[i]>b[cnt]+mid && a[i]<b[cnt]-mid) return false;
  15.    	if(cnt<b.size()-1) cnt++;
  16.    }
  17.   }
  18.   return true;
  19.  }
  20.  
  21. void solve() {
  22.  
  23.    int n,m;
  24.    cin >> n >> m;
  25.    vector<int> cities(n),towers(m);
  26.    for(int i=0;i<n;i++) cin >> cities[i];
  27.    for(int i=0;i<m;i++) cin >> towers[i];
  28.  
  29.    if(m==1){
  30.    	cout << max(abs(cities[0]-towers[0]),abs(cities[n-1]-towers[0]));
  31.    	return;
  32.    }
  33.  
  34.     int low =0;
  35.     int ans =low;
  36.     int high=max(abs(towers[m-1]-cities[0]),abs(cities[m-1]-towers[0]));
  37.     while(low<=high){
  38.       int mid = (low+high)/2;
  39.       if(f(mid,towers,cities)){
  40.         ans =mid;
  41.         high=mid-1;
  42.       }
  43.       else 
  44.        low=mid+1;
  45.     }
  46.  
  47.     cout << ans << '\n';
  48. }
  49.  
  50. int main(){ 
  51.     ios::sync_with_stdio(false);
  52.     cin.tie(nullptr);
  53.  
  54.     /*int t;
  55.     cin >> t;
  56.     while (t--)*/ solve();
  57.  
  58.  
  59.     return 0;
  60. }
  61.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
3 2
-2 2 4
-3 0
stdout
copy 
0
https://ideone.com/iLRa1v
language:
C++ (gcc 8.3)
created:
17 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!