oj.uz

Submission #205628

# Submission time Handle Problem Language Result Execution time Memory
205628 2020-02-29T10:41:39 Z model_code Hiring (IOI09_hiring) C++17
41 / 100
 452 ms 26840 KB 
/**
 * 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);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 256 KB Unexpected end of file - int32 expected
2 Partially correct 5 ms 256 KB Partially correct
3 Incorrect 5 ms 256 KB Unexpected end of file - int32 expected
4 Partially correct 5 ms 256 KB Partially correct
5 Incorrect 5 ms 376 KB Unexpected end of file - int32 expected
6 Partially correct 6 ms 376 KB Partially correct
7 Partially correct 6 ms 376 KB Partially correct
8 Partially correct 6 ms 376 KB Partially correct
9 Partially correct 9 ms 632 KB Partially correct
10 Partially correct 8 ms 632 KB Partially correct
11 Partially correct 9 ms 760 KB Partially correct
12 Incorrect 9 ms 796 KB Unexpected end of file - int32 expected
13 Partially correct 11 ms 760 KB Partially correct
14 Partially correct 14 ms 1144 KB Partially correct
15 Partially correct 16 ms 1144 KB Partially correct

Subtask #2
12.0 / 28.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 256 KB Partially correct
2 Incorrect 5 ms 256 KB Unexpected end of file - int32 expected
3 Partially correct 5 ms 508 KB Partially correct
4 Partially correct 18 ms 1400 KB Partially correct
5 Partially correct 45 ms 3184 KB Partially correct
6 Partially correct 268 ms 15528 KB Partially correct
7 Partially correct 326 ms 22756 KB Partially correct

Subtask #3
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #4
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 376 KB Partially correct
2 Partially correct 6 ms 376 KB Partially correct
3 Partially correct 5 ms 376 KB Partially correct

Subtask #5
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 376 KB Partially correct
2 Partially correct 6 ms 376 KB Partially correct
3 Partially correct 6 ms 376 KB Partially correct

Subtask #6
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 105 ms 6508 KB Partially correct
2 Partially correct 104 ms 6436 KB Partially correct
3 Partially correct 99 ms 6508 KB Partially correct

Subtask #7
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 176 ms 11556 KB Partially correct
2 Partially correct 167 ms 11624 KB Partially correct
3 Partially correct 164 ms 11496 KB Partially correct

Subtask #8
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 404 ms 24416 KB Partially correct
2 Partially correct 395 ms 24416 KB Partially correct
3 Partially correct 398 ms 24548 KB Partially correct

Subtask #9
3.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 448 ms 26708 KB Partially correct
2 Partially correct 452 ms 26840 KB Partially correct
3 Partially correct 439 ms 26580 KB Partially correct