Submission #415288

#	Time	Username	Problem	Language	Result	Execution time	Memory
415288		Antekb	Hiring (IOI09_hiring)	C++14	100 / 100	921 ms	34456 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<pair<ld, int >, pair<int, int> > > V;
    for(int i=0; i<n; i++){
        int a, b;
        cin>>a>>b;
        V.push_back({{a/ld(b), a},  {b, i}});
    }
    sort(V.begin(), V.end());
    set<pair<int, int> > S;
    long long sum=0;
    int l=0;
    long double k=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*V[i].st.nd>w*V[i].nd.st){
            sum-=(*S.crbegin()).st;
            S.erase(S.find(*S.crbegin()));
        }
        if(S.size()>l){
            l=S.size();
            k=sum*V[i].st.nd/ld(V[i].nd.st);
        }
        else if(S.size()== l) k =min(k, sum*V[i].st.nd/ld(V[i].nd.st));
    }
    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*V[i].st.nd>w*V[i].nd.st){
            sum-=(*S.crbegin()).st;
            S.erase(S.find(*S.crbegin()));
        }
        if(S.size()==l && k==sum*V[i].st.nd/ld(V[i].nd.st)){
            for(auto j:S)cout<<j.nd+1<<"\n";
            return 0;
        }
    }
    //cout<<"a";
}

Compilation message (stderr)

hiring.cpp: In function 'int main()':
hiring.cpp:35: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]
   35 |         if(S.size()>l){
      |            ~~~~~~~~^~
hiring.cpp:39:25: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |         else if(S.size()== l) k =min(k, sum*V[i].st.nd/ld(V[i].nd.st));
      |                 ~~~~~~~~^~~~
hiring.cpp:51: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]
   51 |         if(S.size()==l && k==sum*V[i].st.nd/ld(V[i].nd.st)){
      |            ~~~~~~~~^~~

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