oj.uz

Submission #884408

# Submission time Handle Problem Language Result Execution time Memory
884408 2023-12-07T09:55:44 Z rxlfd314 Hiring (IOI09_hiring) C++17
100 / 100
 471 ms 41692 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
using arl4 = array<ll, 4>;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)

#define chmax(a, b) (a = max(1ll * a, 1ll * (b)))
#define chmin(a, b) (a = min(1ll * a, 1ll * (b)))

struct BIT {
  vt<ll> val, cnt;
  BIT(int n) {
    val.resize(n);
    cnt.resize(n);
  }
  void upd(int i, int v) {
    for (; i < size(val); i += i+1 & -i-1)
      val[i] += v, cnt[i]++;
  }
  arl2 qry(ll v) {
    int ii = -1, ret = 0;
    ROF(i, 31 - __builtin_clz(size(val)), 0)
      if (ii + (1 << i) < size(val) && val[ii+(1<<i)] <= v) {
        ret += cnt[ii+=1<<i];
        v -= val[ii];
      }
    return {ret, v};
  }
};

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int N; ll W;
  cin >> N >> W;
  int S[N], Q[N];
  vt<ari2> cmp;
  FOR(i, 0, N-1)
    cin >> S[i] >> Q[i], cmp.push_back({Q[i], i});
  int ord[N];
  iota(ord, ord+N, 0);
  sort(ord, ord+N, [&](const int &a, const int &b) {
    return S[a] * Q[b] < S[b] * Q[a];    
  });
  sort(all(cmp));
  BIT fen(size(cmp));  
  vt<arl4> best;
  FOR(ii, 0, N-1) {
    int i = ord[ii];
    int s = S[i], q = Q[i];
    auto [cnt, cost] = fen.qry(W * q / s - q);
    cost = W * q / s - q - cost;
    best.push_back({cnt + 1, 1ll * s * (q + cost), q, ii});
    fen.upd(lower_bound(all(cmp), ari2{q, i}) - begin(cmp), q);
  }
  sort(all(best), [&](arl4 &a, arl4 &b) {
    return a[0] == b[0] ? a[1] * b[2] < b[1] * a[2] : a[0] > b[0];    
  });
  sort(ord, ord+best[0][3], [&](const int &a, const int &b) {
    return Q[a] < Q[b];    
  });
  cout << best[0][0] << '\n' << ord[best[0][3]] + 1 << '\n';
  FOR(i, 0, best[0][0]-2)
    cout << ord[i] + 1 << '\n';
}

Compilation message

hiring.cpp: In member function 'void BIT::upd(int, int)':
hiring.cpp:27:33: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   27 |     for (; i < size(val); i += i+1 & -i-1)
      |                                ~^~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 512 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 352 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 756 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 1004 KB Output is correct
11 Correct 4 ms 1116 KB Output is correct
12 Correct 4 ms 1116 KB Output is correct
13 Correct 7 ms 1496 KB Output is correct
14 Correct 7 ms 1588 KB Output is correct
15 Correct 9 ms 1752 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 452 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 12 ms 2392 KB Output is correct
5 Correct 39 ms 9292 KB Output is correct
6 Correct 267 ms 33324 KB Output is correct
7 Correct 320 ms 36436 KB Output is correct

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

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

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 11060 KB Output is correct
2 Correct 88 ms 10828 KB Output is correct
3 Correct 84 ms 10268 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 19524 KB Output is correct
2 Correct 151 ms 19520 KB Output is correct
3 Correct 146 ms 19008 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 39596 KB Output is correct
2 Correct 383 ms 39480 KB Output is correct
3 Correct 394 ms 38772 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 41692 KB Output is correct
2 Correct 471 ms 40756 KB Output is correct
3 Correct 450 ms 40412 KB Output is correct