Submission #1036047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036047		12345678	Hiring (IOI09_hiring)	C++17	92 / 100	448 ms	57632 KiB

hiring

#include <bits/stdc++.h>

using namespace std;

const int nx=5e5+5;

#define ll long long

ll n, s[nx], q[nx], mp[nx], w, res[nx];
vector<pair<double, ll>> v;
vector<pair<ll, ll>> vmp;
pair<ll, pair<double, ll>> mx;

struct segtree
{
    int f[4*nx];
    ll d[4*nx];
    void update(int l, int r, int i, int idx, ll vl)
    {
        if (idx<l||r<idx) return;
        if (l==r) return d[i]+=vl, f[i]++, void();
        int md=(l+r)/2;
        update(l, md, 2*i, idx, vl);
        update(md+1, r, 2*i+1, idx, vl);
        d[i]=d[2*i]+d[2*i+1];
        f[i]=f[2*i]+f[2*i+1];
    }
    pair<ll, ll> query(int l, int r, int i, double cost, double mul)
    {
        if (l==r)
        {
            if (f[i]==0) return {0, cost};
            if (cost>=d[i]*mul) return {1, cost-d[i]*mul};
            else return {0, cost};
        }
        int md=(l+r)/2;
        if (d[2*i]*mul>cost) return query(l, md, 2*i, cost, mul);
        else
        {
            auto tmp=query(md+1, r, 2*i+1, cost-d[2*i]*mul, mul);
            return {tmp.first+f[2*i], tmp.second};
        }
    }
} st;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>w;
    for (int i=1; i<=n; i++) cin>>s[i]>>q[i], v.push_back({((double)s[i])/q[i], i}), vmp.push_back({q[i], i});
    sort(vmp.begin(), vmp.end());
    for (int i=1; i<=n; i++) mp[i]=lower_bound(vmp.begin(), vmp.end(), make_pair(q[i], (ll)i))-vmp.begin()+1;
    sort(v.begin(), v.end());
    for (int i=0; i<n; i++)
    {
        ll cnt=1, idx=v[i].second;
        double cost=s[idx];
        if (cost>w) continue;
        
        if (((double)st.d[1])*s[idx]/q[idx]<=w) cost+=((double)st.d[1])*s[idx]/q[idx], cnt+=st.f[1];
        else
        {
            auto tmp=st.query(1, n, 1, w-cost, (double)s[idx]/q[idx]);
            cnt+=tmp.first;
            cost=w-tmp.second;
        }
        mx=max(mx, {cnt, {-cost, i}});
        st.update(1, n, 1, mp[idx], q[idx]);
    }
    cout<<(int)mx.first<<'\n';
    double cost=s[v[mx.second.second].second];
    cout<<v[mx.second.second].second<<'\n';
    vector<pair<ll, ll>> tmp;
    for (int i=0; i<mx.second.second; i++) tmp.push_back({q[v[i].second], v[i].second});
    sort(tmp.begin(), tmp.end());
    reverse(tmp.begin(), tmp.end());
    while (!tmp.empty()&&cost+((double)tmp.back().first)*(s[v[mx.second.second].second])/q[v[mx.second.second].second]<=w) cout<<(int)tmp.back().second<<'\n', cost+=((double)tmp.back().first)*(s[v[mx.second.second].second])/q[v[mx.second.second].second], tmp.pop_back();
}

• Subtask 1: 26 / 30
• Subtask 2: 24 / 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