/**
* Solution to IOI 2009 problem "hiring"
*
* O(NlogN) solution. We process the candidates in increasing
* order of "utility" (where utility is the candidate's minimum
* rate of pay per unit of qualification). If we hire a candidate
* with utility U, then we know that for all candidates with
* utility V < U we'll be able to meet their minimum salary
* requirement. This is because:
*
* V = S1 / Q1 < S2 / Q2 = U
* => S1 < (Q1 / Q2) * S2 = the amount that candidate 1
* will get paid
*
* The speedup to NlogN comes from the fact that we store the
* candidates qualification values in a heap, giving O(logN)
* time to insert them and then O(logN) time to remove over-
* qualified candidates from the heap who are inflating the
* cost too much.
*
* Carl Hultquist, [email protected]
*/
#include <cassert>
#include <cstring>
#include <vector>
#include <algorithm>
#include <utility>
#include <cstdio>
using namespace std;
#define MAX_N 500000
class candidate
{
public:
double s, q, r;
int i;
bool operator < (const candidate &c) const
{
return r < c.r;
}
};
candidate c[MAX_N];
int n;
long long w;
int best = 0;
int bestIndex = 0;
double bestCost = 0;
int main()
{
scanf("%d %lld", &n, &w);
assert(1 <= n && n <= MAX_N);
for (int i = 0; i < n; i++)
{
scanf("%lf %lf", &c[i].s, &c[i].q);
c[i].r = c[i].s / c[i].q;
c[i].i = i + 1;
}
sort(c, c + n);
// We now have a list of the candidates sorted by their utility. We
// process the candidates in this order, and add them to the list of
// candidates chosen. While the set of candidates chosen costs us
// too much, we remove the most qualified candidate (and thus the one
// which is inflating the cost too much).
double totalQual = 0;
vector<double> heapQuals;
heapQuals.reserve(n);
for (int i = 0; i < n; i++)
{
heapQuals.push_back(c[i].q);
push_heap(heapQuals.begin(), heapQuals.end());
totalQual += c[i].q;
double maxQual = w / c[i].r;
while (totalQual > maxQual)
{
totalQual -= heapQuals[0];
pop_heap(heapQuals.begin(), heapQuals.end());
heapQuals.pop_back();
}
// If we have more candidates than we have previously
// seen before, then make a note of the number and of
// the last candidate that we processed.
int num = (int) heapQuals.size();
double cost = totalQual * c[i].r;
if (num > best || (num == best && cost < bestCost))
{
best = num;
bestCost = cost;
bestIndex = i;
}
}
// In order to maintain an O(NlogN) algorithm, we must
// recreate the best set of candidates outside the main
// loop (if we updated it inside the main loop, we could
// trigger O(N) updates giving overall complexity of
// O(N^2)!
vector<pair<double, int> > heap;
bool usedCandidate[n + 1];
memset(usedCandidate, 0, sizeof(usedCandidate));
totalQual = 0;
for (int i = 0; i <= bestIndex; i++)
{
heap.push_back(make_pair(c[i].q, c[i].i));
push_heap(heap.begin(), heap.end());
totalQual += c[i].q;
usedCandidate[c[i].i] = true;
}
// Remove over-qualified candidates
double maxQual = w / c[bestIndex].r;
while (totalQual > maxQual)
{
totalQual -= heap[0].first;
usedCandidate[heap[0].second] = false;
pop_heap(heap.begin(), heap.end());
heap.pop_back();
}
// Output the list of candidates used
printf("%d\n", best);
for (int i = 1; i <= n; i++)
if (usedCandidate[i])
printf("%d\n", i);
return 0;
}
Compilation message
hiring.cpp: In function 'int main()':
hiring.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %lld", &n, &w);
~~~~~^~~~~~~~~~~~~~~~~~~
hiring.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lf %lf", &c[i].s, &c[i].q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Correct |
5 ms |
256 KB |
Output is correct |
| 3 |
Correct |
5 ms |
256 KB |
Output is correct |
| 4 |
Correct |
5 ms |
376 KB |
Output is correct |
| 5 |
Correct |
5 ms |
256 KB |
Output is correct |
| 6 |
Correct |
6 ms |
376 KB |
Output is correct |
| 7 |
Correct |
6 ms |
376 KB |
Output is correct |
| 8 |
Correct |
6 ms |
376 KB |
Output is correct |
| 9 |
Correct |
8 ms |
632 KB |
Output is correct |
| 10 |
Correct |
9 ms |
632 KB |
Output is correct |
| 11 |
Correct |
9 ms |
760 KB |
Output is correct |
| 12 |
Correct |
10 ms |
888 KB |
Output is correct |
| 13 |
Correct |
10 ms |
760 KB |
Output is correct |
| 14 |
Correct |
14 ms |
1144 KB |
Output is correct |
| 15 |
Correct |
15 ms |
1144 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Correct |
5 ms |
256 KB |
Output is correct |
| 3 |
Correct |
5 ms |
256 KB |
Output is correct |
| 4 |
Correct |
18 ms |
1272 KB |
Output is correct |
| 5 |
Correct |
40 ms |
2936 KB |
Output is correct |
| 6 |
Correct |
252 ms |
15080 KB |
Output is correct |
| 7 |
Correct |
315 ms |
22752 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
6508 KB |
Output is correct |
| 2 |
Correct |
96 ms |
6508 KB |
Output is correct |
| 3 |
Correct |
99 ms |
6508 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
172 ms |
11624 KB |
Output is correct |
| 2 |
Correct |
182 ms |
11624 KB |
Output is correct |
| 3 |
Correct |
159 ms |
11624 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
384 ms |
24420 KB |
Output is correct |
| 2 |
Correct |
381 ms |
24416 KB |
Output is correct |
| 3 |
Correct |
382 ms |
24416 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
442 ms |
26528 KB |
Output is correct |
| 2 |
Correct |
457 ms |
26592 KB |
Output is correct |
| 3 |
Correct |
458 ms |
26304 KB |
Output is correct |
