Submission #252338

#	Time	Username	Problem	Language	Result	Execution time	Memory
252338		SamAnd	Hiring (IOI09_hiring)	C++17	60 / 100	344 ms	14076 KiB

hiring

#include <bits/stdc++.h>
using namespace std;
const int N = 500005, M = 20004, m = 20000;
struct ban
{
    int i;
    int s, q;
};
bool operator<(const ban& a, const ban& b)
{
    return (a.s * b.q) < (b.s * a.q);
}
bool so1(const ban& a, const ban& b)
{
    return a.q < b.q;
}

int n;
long long w;
ban a[N];

long long t[N * 4], q[N * 4];

void ubd(int tl, int tr, int x, int pos)
{
    if (tl == tr)
    {
        t[pos] += x;
        q[pos]++;
        return;
    }
    int m = (tl + tr) / 2;
    if (x <= m)
        ubd(tl, m, x, pos * 2);
    else
        ubd(m + 1, tr, x, pos * 2 + 1);
    t[pos] = t[pos * 2] + t[pos * 2 + 1];
    q[pos] = q[pos * 2] + q[pos * 2 + 1];
}

long long qry(int tl, int tr, long double w, long double y, int pos)
{
    if (tl == tr)
    {
        long long u = w / (tl * y);
        return min(u, q[pos]);
    }
    int m = (tl + tr) / 2;
    if (t[pos * 2] * y <= w)
    {
        return q[pos * 2] + qry(m + 1, tr, w - t[pos * 2] * y, y, pos * 2 + 1);
    }
    return qry(tl, m, w, y, pos * 2);
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    #endif // SOMETHING
    scanf("%d%lld", &n, &w);
    for (int i = 1; i <= n; ++i)
    {
        a[i].i = i;
        scanf("%d%d", &a[i].s, &a[i].q);
    }
    sort(a + 1, a + n + 1);
    int ans = -1, ansi;
    for (int i = 1; i <= n; ++i)
    {
        ubd(1, m, a[i].q, 1);
        int yans = qry(1, m, w, a[i].s * 1.0 / a[i].q, 1);
        if (yans > ans)
        {
            ans = yans;
            ansi = i;
        }
    }
    printf("%d\n", ans);
    long double w = ::w;
    long double y = a[ansi].s * 1.0 / a[ansi].q;
    sort(a + 1, a + ansi + 1, so1);
    for (int i = 1; i <= ansi; ++i)
    {
        if (w >= a[i].q * y)
        {
            w -= (a[i].q * y);
            printf("%d\n", a[i].i);
        }
    }
    return 0;
}

Compilation message (stderr)

hiring.cpp: In function 'int main()':
hiring.cpp:61: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:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a[i].s, &a[i].q);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
hiring.cpp:68:19: warning: 'ansi' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int ans = -1, ansi;
                   ^~~~

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