#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <fstream>
#include <queue>
using namespace std;
const int MAXV = 1e9;
const int MAXN = 2005;
int n, a, b;
vector<int> nums;
int idx(int val) {
int ans = INT_MAX;
int lo = 0, hi = n - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (nums[mid] > val) {
hi = mid - 1;
ans = min(ans, mid);
}
else {
lo = mid + 1;
}
}
return ans;
}
bool check(int mid) {
int val = 2 * mid - 1;
int calc1[MAXN], calc2[MAXN];
for (int i = 0; i < n; i++) {
calc2[i] = idx(nums[i] + val);
calc1[i] = idx(nums[i] + mid - 1);
}
int cur = 0;
int c1 = 0, c2 = 0;
while (cur < n) {
if (calc1[cur] == calc2[cur]) {
c1++;
cur = calc1[cur];
}
else {
c2++;
cur = calc2[cur];
}
}
if ((c1 > a && c2 >= b)||(c1 == a && c2 > b)) {
return false;
}
if (c1 <= a && c2 <= b) {
return true;
}
else {
int diff1 = c1 - a, diff2 = c2 - b;
if(diff2 > 0) {
if (diff1 + 2 * diff2 <= 0) {
return true;
}
else {
return false;
}
}
}
return false;
}
int main() {
cin >> n >> a >> b;
for (int i = 0; i < n; i++) {
int temp;
cin >> temp;
nums.push_back(temp);
}
sort(nums.begin(), nums.end());
if (n == 1) {
cout << 1 << endl;
return 0;
}
int lo = 0;
int hi = MAXV;
int ans = INT_MAX;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (check(mid)) {
ans = min(ans, mid);
hi = mid - 1;
}
else {
lo = mid + 1;
}
}
cout << ans << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Execution timed out |
1076 ms |
256 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
