Submission #1088833

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088833		salmon	Hiring (IOI09_hiring)	C++14	100 / 100	406 ms	34724 KiB

hiring

#include <bits/stdc++.h>
using namespace std;

int N;
vector<pair<pair<long long int,long long int>,int>> v;
long long int W;
long long int h1,h2;
priority_queue<pair<long long int,int>,vector<pair<long long int,int>>,greater<pair<long long int,int>>> satprime;
priority_queue<pair<long long int,int>> sat;
vector<pair<pair<long long int, long long int>,int>> nov;

bool c(pair<pair<long long int, long long int>,int> ii1, pair<pair<long long int, long long int>,int> ii2){
    return ii1.first.first * ii2.first.second < ii2.first.first * ii1.first.second;
}

int main(){

    scanf(" %d",&N);
    scanf(" %lld",&W);

    for(int i = 0; i < N; i++){
        scanf(" %lld",&h1);
        scanf(" %lld",&h2);

        v.push_back({{h1,h2},i});
    }

    sort(v.begin(),v.end(),c);

    long long int sum = 0;
    int ans = 0;

    for(int i = 0; i < N; i++){
        if( (sum + v[i].first.second) * v[i].first.first <= W * v[i].first.second){
            while(!satprime.empty() && (satprime.top().first + sum + v[i].first.second) * v[i].first.first <= W * v[i].first.second ){
                sum += satprime.top().first;
                sat.push(satprime.top());
                satprime.pop();
            }
            if(ans == sat.size() + 1){
                nov.push_back({{ (sum + v[i].first.second) * v[i].first.first,v[i].first.second }, i});
            }
            else{
                nov.clear();
                nov.push_back({{ (sum + v[i].first.second) * v[i].first.first,v[i].first.second },i});
            }
            ans = sat.size() + 1;
            //printf("%d %d\n",i,sum+v[i].first.second);
        }

        if(!sat.empty() && v[i].first.second < sat.top().first){
            pair<long long int,int> h = sat.top();
            satprime.push(h);
            sat.pop();
            sat.push({v[i].first.second,v[i].second});

            sum -= h.first;
            sum += v[i].first.second;
        }
        else{
            satprime.push({v[i].first.second,v[i].second});
        }
    }

    printf("%d\n",ans);

    sort(nov.begin(),nov.end(),c);

    int j = nov[0].second;

    while(!sat.empty()){
        sat.pop();
    }
    while(!satprime.empty()){
        satprime.pop();
    }

    sum = 0;

    for(int i = 0; i < N; i++){
        if( (sum + v[i].first.second) * v[i].first.first <= W * v[i].first.second){
            while(!satprime.empty() && (satprime.top().first + sum + v[i].first.second) * v[i].first.first <= W * v[i].first.second ){
                sum += satprime.top().first;
                sat.push(satprime.top());
                satprime.pop();
            }
        }

        if(i == j){
            sat.push({v[i].first.second,v[i].second});
            break;
        }

        if(!sat.empty() && v[i].first.second < sat.top().first){
            pair<long long int,int> h = sat.top();
            satprime.push(h);
            sat.push({v[i].first.second,v[i].second});
            sat.pop();

            sum -= h.first;
            sum += v[i].first.second;
        }
        else{
            satprime.push({v[i].first.second,v[i].second});
        }
    }

    while(!sat.empty()){
        printf("%d\n",sat.top().second + 1);
        sat.pop();
    }
}

Compilation message (stderr)

hiring.cpp: In function 'int main()':
hiring.cpp:40:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::priority_queue<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |             if(ans == sat.size() + 1){
      |                ~~~~^~~~~~~~~~~~~~~~~
hiring.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
hiring.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     scanf(" %lld",&W);
      |     ~~~~~^~~~~~~~~~~~
hiring.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         scanf(" %lld",&h1);
      |         ~~~~~^~~~~~~~~~~~~
hiring.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         scanf(" %lld",&h2);
      |         ~~~~~^~~~~~~~~~~~~

• 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