제출 #532738

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
532738		__Variatto	Hiring (IOI09_hiring)	C++17	41 / 100	1589 ms	14340 KiB

hiring

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int MAX=5e5+10, L=16;
const ll MAXV=1e18+10;
struct st{
    int i, s, q;
}t[MAX];
int n;
ll w;
int minipos;
bool mnie(pair<ll,ll>a, pair<ll, ll>b){
    ll la=a.fi/__gcd(a.fi, a.se), ma=a.se/__gcd(a.fi, a.se);
    ll lb=b.fi/__gcd(b.fi, b.se), mb=b.se/__gcd(b.fi, b.se);
    ll nla=la*mb, nlb=lb*ma;
    return nla>nlb;    
}
bool spr(int x){
    ll sum=0;
    multiset<int>m;
    for(int i=1; i<=x; i++)
        sum+=t[i].q, m.insert(t[i].q);
    pair<ll, ll> mini=make_pair(MAXV, 1);
    for(int i=x; i<=n; i++){
        if(i>x){
            auto it=m.end();
            it--;
            if(*it>t[i].q){
                sum-=*it, sum+=t[i].q;
                m.erase(it), m.insert(t[i].q);
            }
        }
        if(w*(ll)t[i].q>=sum*(ll)t[i].s){
            if(mnie(mini, {sum*(ll)t[i].s, t[i].q}))
                mini={sum*(ll)t[i].s, t[i].q}, minipos=i;
            return true;
        }
    }
    return false;
}
int bin(){
    int pocz=0, kon=n, sr, wyn=0;
    while(pocz<=kon){
        sr=(pocz+kon)/2;
        if(spr(sr))
            wyn=sr, pocz=sr+1;
        else
            kon=sr-1;
    }
    return wyn;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin>>n>>w;
    for(int i=1; i<=n; i++){
        cin>>t[i].s>>t[i].q;
        t[i].i=i;
    }
    sort(t+1, t+n+1, [](st a, st b){
        int la=a.s/__gcd(a.s, a.q), ma=a.q/__gcd(a.s, a.q);
        int lb=b.s/__gcd(b.s, b.q), mb=b.q/__gcd(b.s, b.q);
        int nla=la*mb, nlb=lb*ma;
        return nla<nlb;
    });
    int x=bin();
    cout<<x<<"\n";
    multiset<pair<int,int>>m;
    for(int i=1; i<=minipos; i++)
        m.insert({t[i].q, t[i].i});
    int ile=0;
    for(multiset<pair<int,int>>::iterator it=m.begin(); true; it++){
        cout<<(*it).se<<"\n";
        ile++;
        if(ile==x)
            break;
    }
}

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