#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool isValidGrouping(const vector<int>& abilities, int maxDiff, int A, int B) {
int groupsNeeded = 1, minAbilityInCurrentGroup = abilities[0];
int membersInCurrentGroup = 1;
for (int i = 1; i < abilities.size(); ++i) {
if (abilities[i] - minAbilityInCurrentGroup > maxDiff || membersInCurrentGroup == B) {
++groupsNeeded; // Start a new group
minAbilityInCurrentGroup = abilities[i];
membersInCurrentGroup = 1; // Reset member count for new group
} else {
++membersInCurrentGroup; // Add to current group
}
}
return groupsNeeded <= (abilities.size() + A - 1) / A; // Check if grouping is within constraints
}
int findMinimumMaximumDifference(vector<int>& abilities, int A, int B) {
sort(abilities.begin(), abilities.end());
int low = 0, high = abilities.back() - abilities.front(), result = high;
while (low <= high) {
int mid = low + (high - low) / 2;
if (isValidGrouping(abilities, mid, A, B)) {
result = mid;
high = mid - 1; // Try for a smaller difference
} else {
low = mid + 1; // Need a larger difference
}
}
return result;
}
int main() {
int N, A, B;
cin >> N >> A >> B;
vector<int> abilities(N);
for (int& ability : abilities) {
cin >> ability;
}
cout << findMinimumMaximumDifference(abilities, A, B) << endl;
return 0;
}
Compilation message
plaukimo_varzybos.cpp: In function 'bool isValidGrouping(const std::vector<int>&, int, int, int)':
plaukimo_varzybos.cpp:10:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
10 | for (int i = 1; i < abilities.size(); ++i) {
| ~~^~~~~~~~~~~~~~~~~~
plaukimo_varzybos.cpp:20:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | return groupsNeeded <= (abilities.size() + A - 1) / A; // Check if grouping is within constraints
| ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
23 ms |
1372 KB |
Output is correct |
3 |
Correct |
3 ms |
444 KB |
Output is correct |
4 |
Correct |
295 ms |
10980 KB |
Output is correct |
5 |
Correct |
340 ms |
10988 KB |
Output is correct |
6 |
Correct |
29 ms |
1368 KB |
Output is correct |
7 |
Correct |
319 ms |
9812 KB |
Output is correct |
8 |
Correct |
0 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
23 ms |
1372 KB |
Output is correct |
3 |
Correct |
3 ms |
444 KB |
Output is correct |
4 |
Correct |
295 ms |
10980 KB |
Output is correct |
5 |
Correct |
340 ms |
10988 KB |
Output is correct |
6 |
Correct |
29 ms |
1368 KB |
Output is correct |
7 |
Correct |
319 ms |
9812 KB |
Output is correct |
8 |
Correct |
0 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
23 ms |
1372 KB |
Output is correct |
3 |
Correct |
3 ms |
444 KB |
Output is correct |
4 |
Correct |
295 ms |
10980 KB |
Output is correct |
5 |
Correct |
340 ms |
10988 KB |
Output is correct |
6 |
Correct |
29 ms |
1368 KB |
Output is correct |
7 |
Correct |
319 ms |
9812 KB |
Output is correct |
8 |
Correct |
0 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |