Submission #844026

#	Time	Username	Problem	Language	Result	Execution time	Memory
844026		asdfgrace	Hiring (IOI09_hiring)	C++17	52 / 100	317 ms	65540 KiB

hiring

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


#define DEBUG(x) //x
#define A(x) DEBUG(assert(x))
#define PRINT(x) DEBUG(cerr << x)
#define PV(x) DEBUG(cerr << #x << " = " << x << '\n')
#define PV2(x) DEBUG(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define PAR(x) DEBUG(PRINT(#x << " = { "); for (auto y : x) PRINT(y << ' '); PRINT("}\n");)
#define PAR2(x) DEBUG(PRINT(#x << " = { "); for (auto [y, z] : x) PRINT(y << ',' << z << "  "); PRINT("}\n");)
#define PAR2D(x) DEBUG(PRINT(#x << ":\n"); for (auto arr : x) {PAR(arr);} PRINT('\n'));


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) {
    PV(x); PV(l); PV(r); PV(at);
    int lc = 2 * at, rc = 2 * at + 1, m = (l + r) / 2;
    PV(segtree[lc]);
    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;
  }
};

/*
 * 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
 * i was thinking of a segtree here
 * 
 */

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  cerr << fixed << setprecision(4);
  int n;
  long long w;
  cin >> n >> w;
  vector<int> s(n), q(n), ord(n), ord2(n), at(n), at2(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]; // dollars per Q point
  }
  if ((long long) *max_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[ord[i]] = i;
    at2[ord2[i]] = i;
  }
  PAR(ord); PAR(ord2); PAR(a);
  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];
    PV(units);
    units -= q[i];
    PV(a[i]);
    PV(units);
    int pos = st.find((long long) units, 0, st.n - 1, 1);
    assert(pos >= 0);
    long long val = st.quer(0, pos), num = cnt.quer(0, pos);
    PV(val); PV(num);
    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(at2[i], q[i]);
    cnt.upd(at2[i], 1);
    ++ii;
    PAR(st.segtree); PV(ans);
  }
  vector<pair<int, int>> qi;
  for (int i = 0; i < point; ++i) {
    qi.push_back({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);
    }
  }
  assert(ans == (int) hire.size());
  cout << ans << '\n';
  for (int x : hire) {
    cout << x + 1 << '\n';
  }
}

• Subtask 1: 18 / 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