제출 #1210945

#제출 시각아이디문제언어결과실행 시간메모리
1210945Hamed_GhaffariHiring (IOI09_hiring)C++20
88 / 100
354 ms21264 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; using pld = pair<ll, double>; #define X first #define Y second #define mid ((l+r)>>1) #define lc id<<1 #define rc lc|1 const int MXN = 5e5+5; int n, S[MXN], Q[MXN], cnt[MXN<<2], sum[MXN<<2], ordq[MXN], posq[MXN], ordsq[MXN]; ll W; void upd(int p, int l=1, int r=n+2, int id=1) { if(r-l == 1) { cnt[id] = 1; sum[id] = Q[ordq[l]]; return; } p<mid ? upd(p, l, mid, lc) : upd(p, mid, r, rc); cnt[id] = cnt[lc] + cnt[rc]; sum[id] = sum[lc] + sum[rc]; } pld val; int get(int i, int l=1, int r=n+2, int id=1) { if(r-l == 1) return l; if((1ll*(int(val.Y)+sum[lc])*S[i]+Q[i]-1)/Q[i]<=W) { val.X += cnt[lc]; val.Y += sum[lc]; return get(i, mid, r, rc); } return get(i, l, mid, lc); } int32_t main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); cin >> n >> W; for(int i=1; i<=n; i++) cin >> S[i] >> Q[i]; iota(ordq+1, ordq+n+1, 1); sort(ordq+1, ordq+n+1, [&](int i, int j) { return Q[i] < Q[j]; }); for(int i=1; i<=n; i++) posq[ordq[i]] = i; iota(ordsq+1, ordsq+n+1, 1); sort(ordsq+1, ordsq+n+1, [&](int i, int j) { return S[i]*Q[j] < S[j]*Q[i]; }); pld ans = {0, 0}; pii wh = {0, 0}; for(int i=1; i<=n; i++) { upd(posq[ordsq[i]]); val = {0, 0}; int r = get(ordsq[i]); val.Y = -val.Y * double(S[ordsq[i]]) / double(Q[ordsq[i]]); if(val>ans) { ans = val; wh = {i, r}; } } cout << ans.X << '\n'; for(int i=1; i<=wh.X; i++) if(posq[ordsq[i]]<wh.Y) cout << ordsq[i] << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...