Submission #884408

#	Time	Username	Problem	Language	Result	Execution time	Memory
884408		rxlfd314	Hiring (IOI09_hiring)	C++17	100 / 100	471 ms	41692 KiB

hiring

#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 (stderr)

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 / 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