This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 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... |