Submission #553609

#	Time	Username	Problem	Language	Result	Execution time	Memory
553609		timreizin	Hiring (IOI09_hiring)	C++17	100 / 100	611 ms	43204 KiB

hiring

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <string>
#include <numeric>

using namespace std;

using ll = long long;

struct segtree
{
    int n;
    vector<ll> sum;
    vector<int> counter;
    
    segtree(int n) : n(n)
    {
        sum.resize(4 * n + 5);
        counter.resize(4 * n + 5);
    }
    
    void update(int p, int l, int r, int v)
    {
        if (l > r) return;
        if (l == r)
        {
            sum[v] += p;
            ++counter[v];
            return;
        }
        int m = (l + r) >> 1;
        if (p <= m) update(p, l, m, v << 1);
        else update(p, m + 1, r, v << 1 | 1);
        sum[v] = sum[v << 1] + sum[v << 1 | 1];
        counter[v] = counter[v << 1] + counter[v << 1 | 1];
    }
    
    void update(int p)
    {
        update(p, 0, n - 1, 1);
    }
    
    //first h such that first h have sum > possible
    int get(ll w, ll s, int l, int r, int v)
    {
        if (l > r || sum[v] * s <= w) return -1;
        if (l == r)
        {
            //c * s > w
            //c > w / s
            return w / (s * (sum[v] / counter[v])) + 1;
        }
        int m = (l + r) >> 1;
        if (sum[v << 1] * s > w) return get(w, s, l, m, v << 1);
        return counter[v << 1] + get(w - sum[v << 1] * s, s, m + 1, r, v << 1 | 1);
    }
    
    int get(ll w, ll s)
    {
        return get(w, s, 0, n - 1, 1);
    }
    
    ll getSum(int h, int l, int r, int v)
    {
        if (l > r || h == 0) return 0;
        if (l == r) return h * (sum[v] / counter[v]);
        int m = (l + r) >> 1;
        if (counter[v << 1] >= h) return getSum(h, l, m, v << 1);
        else return sum[v << 1] + getSum(h - counter[v << 1], m + 1, r, v << 1 | 1);
    }
    
    ll getSum(int h)
    {
        return getSum(h, 0, n - 1, 1);
    }
    
};

struct best
{
    int i;
    int h;
    ll n, d;
    
    best(int i, int h, ll n, ll d) : i(i), h(h), n(n), d(d)
    {}
    
    friend bool operator<(best b, best a)
    {
        if (b.h < a.h) return true;
        if (b.h > a.h) return false;
        return b.n * a.d > b.d * a.n;
    }
    
};

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n;
    ll w;
    cin >> n >> w;
    vector<ll> s(n), q(n);
    for (int i = 0; i < n; ++i) cin >> s[i] >> q[i];
    vector<int> inds(n);
    iota(inds.begin(), inds.end(), 0);
    sort(inds.begin(), inds.end(), [&s, &q](int i, int j){ return s[i] * q[j] < s[j] * q[i]; });
    best res{0, 0, 0, 1};
    segtree ds(20001);
    for (int i = 0; i < inds.size(); ++i)
    {
        ds.update(q[inds[i]]);
        int h = ds.get(w * q[inds[i]], s[inds[i]]);
        if (h == -1) h = i + 2;
        --h;
        ll sum = ds.getSum(h);
        res = max(res, {i, h, sum * s[inds[i]], q[inds[i]]});
    }
    set<pair<ll, int>> help;
    for (int i = 0; i <= res.i; ++i) help.insert({q[inds[i]], inds[i]});
    w *= q[inds[res.i]];
    cout << res.h << '\n';
    while (!help.empty())
    {
        auto [v, i] = *help.begin();
        help.erase(help.begin());
        if (v * s[inds[res.i]] > w) break;
        cout << i + 1 << '\n';
        w -= v * s[inds[res.i]];
    }
    return 0;
}

/*
4 100
5 1000
10 100
8 10
20 1
*/

/*
3 4
1 2
1 3
1 3
*/

/*
3 40
10 1
10 2
10 3
*/

Compilation message (stderr)

hiring.cpp: In function 'int main()':
hiring.cpp:113:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |     for (int i = 0; i < inds.size(); ++i)
      |                     ~~^~~~~~~~~~~~~

• 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