Submission #374780

#	Time	Username	Problem	Language	Result	Execution time	Memory
374780		ijxjdjd	Hiring (IOI09_hiring)	C++14	100 / 100	329 ms	39420 KiB

hiring

#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)
#define int ll
using namespace std;

using ll = long long;

struct person {
    ll S, Q;
    ll i;
};
struct ans {
    ll T, S, Q;
    ll tot;
};
bool operator<(const person& lhs, const person& rhs){
    return lhs.S*rhs.Q < rhs.S*lhs.Q;
}
bool operator<(const ans& lhs, const ans& rhs) {
    if (lhs.tot != rhs.tot) {
        return lhs.tot > rhs.tot;
    }
    else {
        return lhs.T*lhs.S*rhs.Q < rhs.T*rhs.S*lhs.Q;
    }
}
const ll MAXS = 20005;
ll sm[4*MAXS];
ll cnt[4*MAXS];
ll W;
ans updMx(person last) {
    ll u = 1;
    ll tl = 0;
    ll tr = MAXS-1;
    ans res = {0, last.S, last.Q, 0};
    while (tl != tr) {
        ll tm = (tl + tr)/2;
        if ((res.T+sm[2*u])*res.S <= W*res.Q) {
            res.tot += cnt[2*u];
            res.T += sm[2*u];
            u = 2*u+1;
            tl = tm+1;
        }
        else {
            tr = tm;
            u = 2*u;
        }
    }
    ll low = 0;
    ll high = cnt[u];
    while (low < high) {
        ll mid = (low + high+1)/2;
        if ((res.T + mid*tl)*res.S <= W*res.Q) {
            low = mid;
        }
        else {
            high = mid-1;
        }
    }
    res.T += low*tl;
    res.tot += low;
    return res;
}
void add(person p) {
    ll u = 1;
    ll tl = 0;
    ll tr = MAXS-1;
    while (true) {
        ll tm = (tl + tr)/2;
        cnt[u]++;
        sm[u] += p.Q;
        if (tl == tr) {
            break;
        }
        if (p.Q <= tm) {
            u = 2*u;
            tr = tm;
        }
        else {
            u = 2*u+1;
            tl = tm+1;
        }

    }
}
signed main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N;
	cin >> N >> W;
	vector<person> per;
	per.resize(N);
	FR(i, N) {
	    per[i].i = i;
        cin >> per[i].S >> per[i].Q;
	}
	sort(all(per));
	vector<pair<ans, int>> pos;
	pos.resize(N);
	for (int i = 0; i < N; i++) {
        add(per[i]);
        pos[i] = {updMx(per[i]), i};
	}
	sort(all(pos));
	sort(per.begin(), per.begin() + pos[0].second+1, [](const person& lhs, const person& rhs) {
        return lhs.Q < rhs.Q;
    });
    cout << pos[0].first.tot << '\n';
	for (int i = 0; i < pos[0].first.tot; i++) {
        cout << per[i].i + 1 << '\n';
	}
	return 0;
}

• 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