# Three Groups MEX

unknown
c_cpp
a year ago
1.4 kB
1
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;
}```