Submission #1166947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166947		julia_08	Hiring (IOI09_hiring)	C++20	34 / 100	1600 ms	131072 KiB

hiring

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

using ll = long long;

const int MAXN = 5e5 + 10;
const int MAXQ = 2e4 + 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;
  }

};

struct node{
  ll sum; int sum_id;
};

worker a[MAXN];

node seg[4 * MAXQ];

int n; ll w;

void update(int x, int lx, int rx, int i){

  if(rx < i || lx > i) return;

  if(lx == rx){
    seg[x].sum += lx;
    seg[x].sum_id ++;
    return;
  }

  int m = (lx + rx) / 2, lc = 2 * x, rc = 2 * x + 1;

  update(lc, lx, m, i);
  update(rc, m + 1, rx, i);

  seg[x].sum = seg[lc].sum + seg[rc].sum;
  seg[x].sum_id = seg[lc].sum_id + seg[rc].sum_id;
}

node merge(node a, node b){
  return {a.sum + b.sum, a.sum_id + b.sum_id};
}

node query(int x, int lx, int rx, int l, int r){

  if(rx < l || lx > r) return {0, 0};

  if(l <= lx && rx <= r) return seg[x];

  int m = (lx + rx) / 2, lc = 2 * x, rc = 2 * x + 1;

  return merge(query(lc, lx, m, l, r), query(rc, m + 1, rx, l, r));
}

int bs(int x, int lx, int rx, ll val){

  if(lx == rx) return lx;

  int m = (lx + rx) / 2, lc = 2 * x, rc = 2 * x + 1;

  if(seg[lc].sum >= val) return bs(lc, lx, m, val);

  return bs(rc, m + 1, rx, val - seg[lc].sum);
}

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);

  ll k = 0;

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

    ll cte = ((w - a[i].s) * a[i].q) / a[i].s;

    int pos = bs(1, 1, MAXQ, cte) - 1;

    node x = query(1, 1, MAXQ, 1, pos);

    k = max(k, x.sum_id + ((cte - x.sum) / (pos + 1)) + 1);

    update(1, 1, MAXQ, a[i].q);

  }

  set<pair<int, int>> s, ans;

  ll 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;

  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;
    }

  }

  cout << k << "\n";

  for(auto [x, i] : ans) cout << i << "\n";

  return 0;
}

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