제출 #532760

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
532760		__Variatto	Hiring (IOI09_hiring)	C++17	84 / 100	1547 ms	26252 KiB

hiring

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

컴파일 시 표준 에러 (stderr) 메시지

hiring.cpp: In function 'int main()':
hiring.cpp:42:24: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   42 |             if(m.size()>=maxi){
      |                ~~~~~~~~^~~~~~
hiring.cpp:43:28: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |                 if(m.size()>maxi)
      |                    ~~~~~~~~^~~~~
hiring.cpp:32:10: warning: unused variable 'udalo' [-Wunused-variable]
   32 |     bool udalo=false;
      |          ^~~~~

• Subtask 1: 30 / 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: 0 / 6
• Subtask 9: 0 / 6