Submission #703271

#	Time	Username	Problem	Language	Result	Execution time	Memory
703271		finn__	Hiring (IOI09_hiring)	C++17	100 / 100	543 ms	38564 KiB

hiring

#include <bits/stdc++.h>
using namespace std;

#define N 500000
#define L (1 << 19)

struct Worker
{
    int64_t s, q;
    size_t i;
};

bool compare_worker(Worker const &a, Worker const &b)
{
    return a.s * b.q > a.q * b.s;
}

bool compare_q(Worker const &a, Worker const &b)
{
    return a.q < b.q;
}

Worker y[N];
size_t ind[N], tree[1 << 20][2];

void tree_set0(size_t i)
{
    i += L;
    tree[i][0] = 0;
    tree[i][1] = 0;
    while (i >>= 1)
    {
        tree[i][0] = tree[2 * i][0] + tree[2 * i + 1][0];
        tree[i][1] = tree[2 * i][1] + tree[2 * i + 1][1];
    }
}

int main()
{
    size_t n;
    int64_t w;
    cin >> n >> w;

    for (size_t i = 0; i < n; ++i)
    {
        cin >> y[i].s >> y[i].q;
        y[i].i = i;
    }
    sort(y, y + n, compare_q);

    for (size_t i = 0; i < n; ++i)
        tree[L + i][0] = y[i].q, tree[L + i][1] = 1, ind[y[i].i] = i;
    for (size_t i = L - 1; i; --i)
    {
        tree[i][0] = tree[2 * i][0] + tree[2 * i + 1][0];
        tree[i][1] = tree[2 * i][1] + tree[2 * i + 1][1];
    }

    sort(y, y + n, compare_worker);
    size_t max_workers = 0, limiting = SIZE_MAX;
    long double min_c = DBL_MAX;

    for (size_t i = 0; i < n; ++i)
    {
        tree_set0(ind[y[i].i]);
        // Walk down the segment tree until sum(q2) * s1 > w * q1.
        size_t j = 1, pre_nonzero = 1;
        int64_t c = y[i].s * y[i].q;
        while (j < L)
        {
            if (c + tree[2 * j][0] * y[i].s <= w * y[i].q)
            {
                pre_nonzero += tree[2 * j][1];
                c += tree[2 * j][0] * y[i].s;
                j = j * 2 + 1;
            }
            else
                j = 2 * j;
        }
        if (pre_nonzero > max_workers || (pre_nonzero == max_workers && (long double)c / (long double)y[i].q < min_c))
            max_workers = pre_nonzero, min_c = (long double)c / (long double)y[i].q, limiting = i;
    }

    cout << max_workers << '\n';
    sort(y + limiting + 1, y + n, compare_q);
    for (size_t i = limiting; i < limiting + max_workers; ++i)
        cout << y[i].i + 1 << '\n';
}

Compilation message (stderr)

hiring.cpp: In function 'int main()':
hiring.cpp:71:45: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'int64_t' {aka 'long int'} [-Wsign-compare]
   71 |             if (c + tree[2 * j][0] * y[i].s <= w * y[i].q)
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 28 / 28
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 6 / 6
• Subtask 7: 6 / 6
• Subtask 8: 6 / 6
• Subtask 9: 6 / 6