Submission #844030

#	Time	Username	Problem	Language	Result	Execution time	Memory
844030		asdfgrace	Hiring (IOI09_hiring)	C++17	100 / 100	463 ms	39860 KiB

hiring

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

/*
 * for (each prefix i)
 * sort prefix by q-value
 * get last prefix sum after the sorting that is less than or equal to
 * the number of remaining units
 * replicate with segtree (indices sorted by q[i])
 * binary search by walking on segtree
 */

template <class T> struct SegTree {
  T comb(T a, T b) {
    return a + b;
  }
  const T init = 0;
  vector<T> segtree;
  int n;
  
  SegTree(int len) {
    n = 1;
    while (n < len) n <<= 1;
    segtree = vector<T>(n * 2, init);
  }
  
  void upd(int k, T x) {
    k += n;
    segtree[k] = x;
    for (k /= 2; k >= 1; k /= 2) {
      segtree[k] = comb(segtree[2 * k], segtree[2 * k + 1]);
    }
  }
  
  int find(int x, int l, int r, int at) {
    int lc = 2 * at, rc = 2 * at + 1, m = (l + r) / 2;
    if (l == r) return (segtree[at] <= x ? l : l - 1);
    if (segtree[lc] >= x) {
      return find(x, l, m, lc);
    } else {
      return find(x - segtree[lc], m + 1, r, rc);
    }
  }
  
  T quer(int l, int r) {
    T res = init;
    l += n; r += n;
    for (; l <= r && l > 0 && r > 0 ; l >>= 1, r >>= 1) {
      if (l & 1) res = comb(res, segtree[l++]);
      if (!(r & 1)) res = comb(res, segtree[r--]);
    }
    return res;
  }
};

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n;
  long long w;
  cin >> n >> w;
  vector<int> s(n), q(n), ord(n), ord2(n), at(n);
  vector<long double> a(n);
  iota(ord.begin(), ord.end(), 0);
  iota(ord2.begin(), ord2.end(), 0);
  for (int i = 0; i < n; ++i) {
    cin >> s[i] >> q[i];
    a[i] = (long double) s[i] / (long double) q[i];
  }
  if ((long long) *min_element(s.begin(), s.end()) > w) {
    cout << 0 << '\n';
    return 0;
  }
  sort(ord.begin(), ord.end(), [&](int x, int y) {
    return a[x] < a[y] || (a[x] == a[y] && q[x] < q[y]);
  });
  sort(ord2.begin(), ord2.end(), [&](int x, int y) {
    return q[x] < q[y];
  });
  for (int i = 0; i < n; ++i) {
    at[ord2[i]] = i;
  }
  SegTree<long long> st(n), cnt(n);
  int ans = 0, point = 0;
  long double cost = 1e18;
  int ii = 0;
  for (int i : ord) {
    long double units = (long double) w / (long double) a[i];
    units -= q[i];
    int pos = st.find((long long) units, 0, st.n - 1, 1);
    long long val = st.quer(0, pos), num = cnt.quer(0, pos);
    if (num + 1 > ans || (num + 1 == ans && a[i] * (val + q[i]) < cost)) {
      ans = num + 1;
      point = ii;
      cost = a[i] * (val + q[i]);
    }
    st.upd(at[i], q[i]);
    cnt.upd(at[i], 1);
    ++ii;
  }
  vector<pair<int, int>> qi(point);
  for (int i = 0; i < point; ++i) {
    qi[i] = {q[ord[i]], ord[i]};
  }
  sort(qi.begin(), qi.end());
  vector<int> hire(1, ord[point]);
  long double c = s[ord[point]];
  for (int i = 0; i < point; ++i) {
    if (c + qi[i].first * a[ord[point]] <= (long double) w) {
      c += qi[i].first * a[ord[point]];
      hire.push_back(qi[i].second);
    }
  }
  cout << ans << '\n';
  for (int x : hire) {
    cout << x + 1 << '\n';
  }
  return 0;
}

• 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