Advertisement
Beingamanforever

Edu Div2 B

Oct 28th, 2024 (edited)
62
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.80 KB | None | 0 0
  1.  
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
  5. #define NeedForSpeed                  \
  6.     ios_base::sync_with_stdio(false); \
  7.     cin.tie(NULL);                    \
  8.     cout.tie(NULL);
  9. #define int long long
  10. #define all(x) (x).begin(), (x).end()
  11. typedef vector<int> vi;
  12. typedef vector<bool> vb;
  13. typedef vector<vi> vvi;
  14. typedef vector<pair<int, int>> vpi;
  15. #define f first
  16. #define s second
  17. #define endl "\n"
  18. const int mod = 1000000007;
  19. int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
  20. void solve()
  21. {
  22.     int n;
  23.     cin >> n;
  24.     vi v(n);
  25.     for (int i = 0; i < n; i++)
  26.     {
  27.         cin >> v[i];
  28.     }
  29.     sort(all(v));
  30.     if (n == 1)
  31.     {
  32.         cout << 1 << endl;
  33.         return;
  34.     }
  35.     if (n == 1)
  36.     {
  37.         cout << abs(v[1] - v[0]) << endl;
  38.         return;
  39.     }
  40.     if ((n % 2) == 0)
  41.     {
  42.         // only 1 answer is possible
  43.         int ans = 0;
  44.         for (int i = 0; i < n; i += 2)
  45.         {
  46.             ans = max(ans, (v[i + 1] - v[i]));
  47.         }
  48.         cout << ans << endl;
  49.     }
  50.     else
  51.     {
  52.         // leave 1 element and do the same, as we can get a number closed to it
  53.         int ans = 1e18;
  54.         for (int i = 0; i < n; i += 2)
  55.         {
  56.             int ma1 = 0, ma2 = 0;
  57.             for (int j = 0; j < i; j += 2)
  58.             {
  59.                 ma1 = max(ma1, v[j + 1] - v[j]);
  60.             }
  61.             for (int j = i + 1; j < n; j += 2)
  62.             {
  63.                 ma2 = max(ma2, v[j + 1] - v[j]);
  64.             }
  65.             ans = min(ans, max(ma1, ma2));
  66.         }
  67.         cout << ans << endl;
  68.     }
  69.     return;
  70. }
  71.  
  72. signed main()
  73. {
  74.     NeedForSpeed;
  75.     int t = 1;
  76.     cin >> t;
  77.     while (t--)
  78.     {
  79.         solve();
  80.     }
  81.     return 0;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement