제출 #798212

#제출 시각아이디문제언어결과실행 시간메모리
798212HaroldVemenoHiring (IOI09_hiring)C++17
30 / 100
238 ms16004 KiB
#include <bits/stdc++.h> #ifdef GUDEB #define D(x) cerr << #x << ": " << (x) << '\n'; #define ifdeb if(true) #else #define D(x) ; #define ifdeb if(false) #endif #define all(x) begin(x), end(x) using namespace std; using ull = unsigned long long; using ll = long long; // #define int ll; struct Z { int c; int q; }; int s; ll zsi[4400000]; ll csi[4400000]; pair<ll, ll> fbz(ll m, int u, int ub, int ue) { if(ub == ue-1) return {0, 0}; int um = (ub+ue)/2; if(csi[2*u] > m) return fbz(m, 2*u, ub, um); auto [rz, rc] = fbz(m-csi[2*u], 2*u+1, um, ue); return {rz + zsi[2*u], rc + csi[2*u]}; } void solve() { int n; ll m; cin >> n >> m; vector<Z> zs(n); for(int i = 0; i < n; ++i) { cin >> zs[i].c; cin >> zs[i].q; } vector<int> bp(n); iota(all(bp), 0); sort(all(bp), [&zs](int ai, int bi){ Z& a = zs[ai]; Z& b = zs[bi]; return 1ll*a.c*b.q < 1ll*b.c*a.q; }); ll mz = 0; s = 1 << 20; int bi = 0; ll mcn = 0; ll mcd = 1; ll mcq = 0; for(int i = 0; i < n; ++i) { Z& z = zs[bp[i]]; zsi[s+z.q] += 1; csi[s+z.q] += z.q; for(int j = (s + z.q)/2; j > 0; j /= 2) { zsi[j] = zsi[2*j] + zsi[2*j+1]; csi[j] = csi[2*j] + csi[2*j+1]; } auto [fz, fc] = fbz(m*z.q/z.c, 1, 0, s); ll fcn = fc * z.c; ll fcd = z.q; if(fz > mz) { mz = fz; mcn = fcn; mcd = fcd; mcq = fc; bi = i; } else if(fz == mz && fcn*mcd < mcn*fcd) { mcn = fcn; mcd = fcd; bi = i; mcq = fc; } } { ll g = gcd(mcd, mcd); mcd /= g; mcn /= g; } if(mcd == 1) cout << mz << ' ' << mcn << '\n'; else cout << mz << ' ' << mcn << '/' << mcd << '\n'; vector<int> is(bi+1); iota(all(is), 0); sort(all(is), [&zs, &bp](int ai, int bi){ Z& a = zs[bp[ai]]; Z& b = zs[bp[bi]]; return a.q < b.q; }); ll sq = 0; vector<int> con; D(mcq) for(int i = 0; sq < mcq; ++i) { D(sq) con.push_back(bp[is[i]]); sq += zs[bp[is[i]]].q; } sort(all(con)); for(int a : con) cout << a+1 << ' '; cout << '\n'; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout << setprecision(20); solve(); }
#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...