Submission #1166977

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166977		julia_08	Hiring (IOI09_hiring)	C++20	88 / 100	327 ms	21872 KiB

hiring

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

using ll = long long;

const int MAXN = 5e5 + 10;

struct worker{
  int s, q, id;

  bool operator < (worker b){
    if((ll) s * b.q != (ll) b.s * q) return (ll) s * b.q < (ll) b.s * q;
    return id < b.id;
  }

};

worker a[MAXN];

int n; ll w;

int main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> w;

  for(int i=1; i<=n; i++){
    cin >> a[i].s >> a[i].q;
    a[i].id = i;
  }

  sort(a + 1, a + n + 1);

  int k = 0;

  ll sum = 0;

  priority_queue<ll> q;

  for(int i=1; i<=n; i++){

    while(!q.empty() && (sum * a[i].s) > ((w - a[i].s) * a[i].q)){
      sum -= q.top();
      q.pop();
    }

    k = max(k, (int) q.size() + 1);

    q.push(a[i].q);
    sum += a[i].q;

  }

  set<pair<int, int>> s;

  sum = 0;

  for(int i=1; i<k; i++){
    s.insert({a[i].q, a[i].id});
    sum += a[i].q;
  }

  ll num = 1e18, den = 1;

  int id = k;

  for(int i=k; i<=n; i++){

    ll cur_num = a[i].s * (sum + a[i].q), cur_den = a[i].q;

    if(cur_num * den < num * cur_den){
      num = cur_num, den = cur_den;
      id = i;
    }

    if(a[i].q < (*s.rbegin()).first){
      sum -= (*s.rbegin()).first;
      s.erase(*s.rbegin());

      s.insert({a[i].q, a[i].id});
      sum += a[i].q;
    }

  }

  vector<pair<int, int>> workers;

  for(int i=1; i<id; i++){
    workers.push_back({a[i].q, a[i].id});
  }

  sort(workers.begin(), workers.end());

  cout << k << "\n";

  cout << a[id].id << "\n";

  for(int i=0; i<k-1; i++) cout << workers[i].second << "\n";

  return 0;
}

• Subtask 1: 28 / 30
• Subtask 2: 24 / 28
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 0 / 6
• Subtask 7: 6 / 6
• Subtask 8: 6 / 6
• Subtask 9: 6 / 6