fork download
copy 
  1. #include <bits/stdc++.h> // NeOWami
  2. #include <numeric>
  3. using namespace std;
  4.  
  5. #define ft first
  6. #define sc second
  7. #define int long long
  8. using ull = unsigned long long;
  9. using U = make_unsigned_t<long long>;
  10. const int N = 1e5 + 5;
  11. int n, L, R;
  12. int a[N];
  13. int ans, postmp, len;
  14. ull maxLen = 0;
  15. bool ckmax(ull &u, ull v) {
  16.     if (u < v) return u = v, 1;
  17.     return 0; 
  18. }
  19. int half_diff(int l, int r) {
  20.     U diff = U(r) - U(l);
  21.     return (int)(diff >> 1);
  22. }
  23. ull getLen(int l, int r) {
  24.     return U(r) - U(l);
  25. }
  26. signed main() {
  27.     cin.tie(NULL)->sync_with_stdio(false);
  28.     if(ifstream("MAXDIS.inp")) {
  29.         freopen("MAXDIS.inp", "r", stdin);
  30.         freopen("MAXDIS.out", "w", stdout);
  31.     }
  32.     cin >> n >> L >> R;
  33.     for (int i = 1; i <= n; i++) cin >> a[i];
  34.     sort(a + 1, a + n + 1);
  35.     ans = R;
  36.     // L <= a[sta], a[en] <= R
  37.     int sta = lower_bound(a + 1, a + n + 1, L) - a, en = upper_bound(a + 1, a + n + 1, R) - a - 1;
  38.     // calc from a[en] -> R
  39.     if (en < n) {
  40.         // R kẹt ở giữa 2 a[X], a[Y]
  41.         len = half_diff(a[en], a[en + 1]);
  42.         postmp = max(L, min(R, max(a[en + 1] - len, a[en] + len)));
  43.         if (ckmax(maxLen, min(getLen(postmp, a[en + 1]), getLen(a[en], postmp)))) ans = postmp;
  44.     }
  45.     else {
  46.         // R nằm sau A[n];
  47.         if (ckmax(maxLen, R - a[n])) ans = R;
  48.     }
  49.  
  50.     // calc from a[sta] -> a[en];
  51.     for (int i = en; i >= sta + 1; i--) {
  52.         if (ckmax(maxLen, half_diff(a[i - 1], a[i]))) ans = max(a[i] - maxLen, a[i - 1] + maxLen);
  53.     }
  54.  
  55.     // calc from L -> a[sta]
  56.     if (sta > 1) {
  57.         // L kẹt ở giữa 2 a[X], a[Y]
  58.         len = half_diff(a[sta - 1], a[sta]);
  59.         postmp = min(R, max(L, max(a[sta] - len, a[sta - 1] + len)));
  60.         if (ckmax(maxLen, min(getLen(postmp, a[sta]), getLen(a[sta - 1], postmp)))) ans = postmp;
  61.     }
  62.     else {
  63.         // L bé hơn a[1];
  64.         if (ckmax(maxLen, a[1] - L)) ans = L;
  65.     }
  66.     cout << ans;
  67.     return 0;
  68. }
  69.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/8HqbLw
language:
C++14 (gcc 8.3)
created:
18 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!