oj.uz

Submission #844030

# Submission time Handle Problem Language Result Execution time Memory
844030 2023-09-04T23:16:50 Z asdfgrace Hiring (IOI09_hiring) C++17
100 / 100
 463 ms 39860 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 3 ms 856 KB Output is correct
10 Correct 3 ms 856 KB Output is correct
11 Correct 3 ms 1112 KB Output is correct
12 Correct 4 ms 1112 KB Output is correct
13 Correct 5 ms 1112 KB Output is correct
14 Correct 7 ms 1368 KB Output is correct
15 Correct 8 ms 1624 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 11 ms 2392 KB Output is correct
5 Correct 32 ms 6992 KB Output is correct
6 Correct 239 ms 30416 KB Output is correct
7 Correct 336 ms 35020 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 9684 KB Output is correct
2 Correct 76 ms 9684 KB Output is correct
3 Correct 75 ms 9684 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 17872 KB Output is correct
2 Correct 135 ms 17856 KB Output is correct
3 Correct 125 ms 17868 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 36996 KB Output is correct
2 Correct 357 ms 37168 KB Output is correct
3 Correct 371 ms 36944 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 39740 KB Output is correct
2 Correct 463 ms 39860 KB Output is correct
3 Correct 425 ms 39740 KB Output is correct