이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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';
}
컴파일 시 표준 에러 (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)
| ~^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |