Submission #557856

#	Time	Username	Problem	Language	Result	Execution time	Memory
557856		kevinxiehk	Hiring (IOI09_hiring)	C++17	100 / 100	461 ms	29740 KiB

hiring

#include <bits/stdc++.h>
#define mp make_pair
#define pb emplace_back
#define fi first
#define se second
#define int long long
#define inf 1e18
#define ick cout<<"ickbmi32.9\n"
using namespace std;
pair<pair<int, int>, int> arr[500005];
int n, w;
bool cmp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
    return a.fi.se * b.fi.fi > b.fi.se * a.fi.fi;
}
bool le(pair<int, int> a, pair<int, int> b) {
    return a.se * b.fi > b.se * a.fi;
}
signed main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    cin >> n >> w;
    for(int i = 0; i < n; i++) {
        cin >> arr[i].fi.fi >> arr[i].fi.se;
        arr[i].se = i + 1;
    }
    sort(arr, arr + n, cmp);
    priority_queue<pair<int, int>> in;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> out;
    int sum = 0;
    int ans = 0;
    int ls = -1;
    pair<int, int> mc = mp(1000000000, 1);
    for(int i = 0; i < n; i++) {
        in.push(mp(arr[i].fi.se, arr[i].se));
        sum += arr[i].fi.se;
        int a = w * arr[i].fi.se / arr[i].fi.fi;
        while(sum > a) {
            sum -= in.top().fi;
            out.push(in.top());
            in.pop();
        }
        while(!out.empty() && sum + out.top().fi <= a) {
            sum += out.top().fi;
            in.push(out.top());
            out.pop();
        }
        if(in.size() > ans) {
            ls = i;
            mc = mp(sum * arr[i].fi.fi, arr[i].fi.se);
        }
        else if(in.size() == ans && le(mp(sum * arr[i].fi.fi, arr[i].fi.se), mc)) {
            ls = i;
            mc = mp(sum * arr[i].fi.fi, arr[i].fi.se);
        }
        ans = max(ans, (int)in.size());
    }
    cout << ans << '\n';
    while(!in.empty()) in.pop();
    while(!out.empty()) out.pop();
    sum = 0;
    for(int i = 0; i <= ls; i++) {
        in.push(mp(arr[i].fi.se, arr[i].se));
        sum += arr[i].fi.se;
        int a = w * arr[i].fi.se / arr[i].fi.fi;
        while(sum > a) {
            sum -= in.top().fi;
            out.push(in.top());
            in.pop();
        }
        while(!out.empty() && sum + out.top().fi <= a) {
            sum += out.top().fi;
            in.push(out.top());
            out.pop();
        }
    }
    while(!in.empty()) {
        cout << in.top().se << '\n';
        in.pop();
    }
    return 0;
}

Compilation message (stderr)

hiring.cpp: In function 'int main()':
hiring.cpp:47:22: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   47 |         if(in.size() > ans) {
      |            ~~~~~~~~~~^~~~~
hiring.cpp:51:27: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   51 |         else if(in.size() == ans && le(mp(sum * arr[i].fi.fi, arr[i].fi.se), mc)) {
      |                 ~~~~~~~~~~^~~~~~

• 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