nlogn approach for the awesome problem **2226C**. Binary search the answer.↵
↵
~~~~~↵
bool check_k(int a[], int n, int k) {↵
vector<int> leftover;↵
vector<int> mex(k, 0);↵
↵
for (int i = 0; i < n; i++)↵
if (a[i] < k && !mex[a[i]])↵
mex[a[i]] = 1;↵
else↵
leftover.push_back(a[i]);↵
↵
int i = 0, j = 0;↵
while (i < k && j < leftover.size()) {↵
while (i < k && mex[i]) i++;↵
↵
if (i < k && leftover[j] > 2 * i) mex[i] = 1;↵
j++;↵
}↵
while (i < k && mex[i]) i++;↵
↵
return i == k;↵
}↵
↵
int main() {↵
std::ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t;↵
cin >> t;↵
↵
while (t--) {↵
int n;↵
cin >> n;↵
↵
int a[n];↵
for (int& x : a) cin >> x;↵
std::sort(a, a + n);↵
↵
int l = 1, r = n;↵
while (l <= r) {↵
int k = (l + r) / 2;↵
bool res = check_k(a, n, k);↵
↵
if (res)↵
l = k + 1;↵
else↵
r = k - 1;↵
}↵
↵
cout << r << endl;↵
}↵
}↵
~~~~~↵
↵
↵
~~~~~↵
bool check_k(int a[], int n, int k) {↵
vector<int> leftover;↵
vector<int> mex(k, 0);↵
↵
for (int i = 0; i < n; i++)↵
if (a[i] < k && !mex[a[i]])↵
mex[a[i]] = 1;↵
else↵
leftover.push_back(a[i]);↵
↵
int i = 0, j = 0;↵
while (i < k && j < leftover.size()) {↵
while (i < k && mex[i]) i++;↵
↵
if (i < k && leftover[j] > 2 * i) mex[i] = 1;↵
j++;↵
}↵
while (i < k && mex[i]) i++;↵
↵
return i == k;↵
}↵
↵
int main() {↵
std::ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t;↵
cin >> t;↵
↵
while (t--) {↵
int n;↵
cin >> n;↵
↵
int a[n];↵
for (int& x : a) cin >> x;↵
std::sort(a, a + n);↵
↵
int l = 1, r = n;↵
while (l <= r) {↵
int k = (l + r) / 2;↵
bool res = check_k(a, n, k);↵
↵
if (res)↵
l = k + 1;↵
else↵
r = k - 1;↵
}↵
↵
cout << r << endl;↵
}↵
}↵
~~~~~↵
↵
