oj.uz

Submission #844027

# Submission time Handle Problem Language Result Execution time Memory
844027 2023-09-04T23:05:28 Z asdfgrace Hiring (IOI09_hiring) C++17
100 / 100
 441 ms 43700 KB 
#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) *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[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);
    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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 2 ms 600 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 860 KB Output is correct
12 Correct 4 ms 1112 KB Output is correct
13 Correct 5 ms 1368 KB Output is correct
14 Correct 7 ms 1624 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 1 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 11 ms 2396 KB Output is correct
5 Correct 34 ms 7248 KB Output is correct
6 Correct 224 ms 31764 KB Output is correct
7 Correct 312 ms 37724 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 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 756 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 348 KB Output is correct
3 Correct 1 ms 600 KB Output is correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 10188 KB Output is correct
2 Correct 77 ms 10268 KB Output is correct
3 Correct 75 ms 10152 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 18888 KB Output is correct
2 Correct 129 ms 19008 KB Output is correct
3 Correct 145 ms 19144 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 364 ms 41012 KB Output is correct
2 Correct 370 ms 40708 KB Output is correct
3 Correct 375 ms 40384 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 43700 KB Output is correct
2 Correct 438 ms 42688 KB Output is correct
3 Correct 441 ms 42924 KB Output is correct