Three Groups MEX
c_cpp
2 months ago
1.4 kB
0
Indexable
Never
#include <bits/stdc++.h> #define F first #define S second #define PB push_back #define MP make_pair #define MOD (int) 1e9 + 7 #define all(x) begin(x), end(x) typedef long long ll; using namespace std; template <typename T> // cin >> vector<T> istream &operator>>(istream &istream, vector<T> &v) { for (auto &it : v) cin >> it; return istream; } template <typename T> // cout << vector<T> ostream &operator<<(ostream &ostream, const vector<T> &c) { for (auto &it : c) cout << it << " "; return ostream; } bool ok(vector<int>& a, int x) { int mn = INT_MAX, mx = INT_MIN; int partitions = 0; for(int i = 0; i < a.size(); i++) { mn = min(a[i], mn); mx = max(a[i], mx); if(mx - mn > x) { partitions++; mn = a[i]; mx = a[i]; } } return partitions <= 2; } void solve(void) { int n; cin >> n; vector<int> a(n); cin >> a; sort(all(a)); int l = 0, r = *max_element(all(a)) - *min_element(all(a)); while(r - l > 1) { int m = (l + r) >> 1; if(ok(a, m)) { r = m; } else l = m + 1; } if(ok(a, l)) { cout << l; } else cout << r; } int main() { ios::sync_with_stdio(0); cin.tie(0); solve(); return 0; }