Submission #415285

#	Time	Username	Problem	Language	Result	Execution time	Memory
415285		Antekb	Hiring (IOI09_hiring)	C++14	60 / 100	945 ms	29088 KiB

hiring

#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
typedef long double ld;
int main(){
    int n;
    long long w;
    cin>>n>>w;
    vector<pair<ld, pair<int, int> > > V;
    for(int i=0; i<n; i++){
        int a, b;
        cin>>a>>b;
        V.push_back({a/ld(b),  {b, i}});
    }
    sort(V.begin(), V.end());
    set<pair<int, int> > S;
    long long sum=0;
    int l=0;
    for(int i=0; i<n; i++){
        S.insert(V[i].nd);
        sum+=V[i].nd.st;
        /*while(S.size()&& S2.size() && *S2.begin()<*S.crbegin()){
            sum-=(*S.crbegin()).st;
            sum+=(*S.crbegin()).st;
            S.insert(*S2.begin());
            S2.erase(*S2.begin());

        }*/
        while(S.size() && sum>w/V[i].st){
            sum-=(*S.crbegin()).st;
            S.erase(S.find(*S.crbegin()));
        }
        l=max(l, (int)S.size());
    }
    cout<<l<<"\n";
    S.clear();
    sum=0;
    for(int i=0; i<n; i++){
        S.insert(V[i].nd);
        sum+=V[i].nd.st;
        while(S.size() && sum>w/V[i].st){
            sum-=(*S.crbegin()).st;
            S.erase(S.find(*S.crbegin()));
        }
        if(S.size()==l){
            for(auto i:S)cout<<i.nd+1<<"\n";
            return 0;
        }
    }
    //cout<<"a";
}

Compilation message (stderr)

hiring.cpp: In function 'int main()':
hiring.cpp:46:20: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |         if(S.size()==l){
      |            ~~~~~~~~^~~

• 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