Submission #1165868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165868		julia_08	Hiring (IOI09_hiring)	C++20	60 / 100	1595 ms	29616 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;

ll num, den;

set<pair<int, int>> ans;

bool cmp(pair<int, int> x, pair<int, int> y){
  return (ll) x.first * y.second < (ll) y.first * x.second;
}

bool check(int k){
  
  set<pair<int, int>> s;
  
  ll sum = 0;
  
  for(int i=1; i<k; i++){
    s.insert({a[i].q, a[i].id});
    sum += a[i].q;
  }
  
  num = 1e18, den = 1;
  
  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;
      ans = s; ans.insert({a[i].q, a[i].id});
    } 
  
    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;
    }
    
  }
  
  return num <= w * den; 
}

void bs(){
  
  int l = 0, r = n;
  
  while(l < r){
    int m = l + (r - l + 1) / 2;
    if(check(m)) l = m;
    else r = m - 1;
  }
  
  check(l);
}

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);
  
  bs();
  
  cout << ans.size() << "\n";
  
  for(auto [x, i] : ans) cout << i << "\n";
  
  return 0;
}

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