Submission #997382

#	Time	Username	Problem	Language	Result	Execution time	Memory
997382		Ghetto	Hiring (IOI09_hiring)	C++17	53 / 100	581 ms	65536 KiB

hiring

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ldouble = long double;
using pli = pair<ldouble, int>;
const int MAX_N = 5e5 + 5, MAX_S = 2e4 + 5;

int n, m;
int p[MAX_N], s[MAX_N];
pli a[MAX_N];

struct Node {
    int count, sum;
    Node operator+(Node other) { return {count + other.count, sum + other.sum}; };
};
Node st[4 * MAX_S];
void update(int i, int u = 1, int lo = 1, int hi = MAX_S) {
    if (i < lo || hi < i) return;
    if (lo == hi) { st[u] = {st[u].count + 1, st[u].sum + i}; return; };
    int mid = (lo + hi) / 2;
    update(i, 2 * u, lo, mid), update(i, 2 * u + 1, mid + 1, hi);
    st[u] = st[2 * u] + st[2 * u + 1];
}
Node query(int l, int r, int u = 1, int lo = 1, int hi = MAX_S) {
    if (r < lo || hi < l) return {0, 0};
    if (l <= lo && hi <= r) return st[u];
    int mid = (lo + hi) / 2;
    return query(l, r, 2 * u, lo, mid) + query(l, r, 2 * u + 1, mid + 1, hi);
}
int walk(ldouble x, int u = 1, int lo = 1, int hi = MAX_S) {
    if (lo == hi && st[u].sum > x) return -1;
    if (lo == hi) return lo;
    int mid = (lo + hi) / 2;
    if (st[2 * u].sum > x) return walk(x, 2 * u, lo, mid);
    int ans = walk(x - st[2 * u].sum, 2 * u + 1, mid + 1, hi);
    if (ans == -1) return walk(x, 2 * u, lo, mid);
    return ans;
}

struct Answer {
    int count;
    ldouble sum;
    bool is_worse(Answer other) {
        if (count == other.count) return sum > other.sum;
        return count < other.count;
    }
};

signed main() {
    // freopen("hiring.in", "r", stdin), freopen("hiring.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> p[i] >> s[i];
        a[i] = {p[i] / (ldouble) s[i], i};
    }
    sort(a + 1, a + n + 1);

    Answer ans = {0, 0};
    int opt = -1;
    for (int j = 1; j <= n; j++) {
        int i = a[j].second;
        update(s[i]);
        
        ldouble tar = m / a[j].first;
        int ind = walk(tar);
        if (ind == -1) continue;
        Answer new_ans = {query(1, ind).count, query(1, ind).sum * a[j].first};
        
        if (new_ans.is_worse(ans)) continue;
        ans = new_ans, opt = j;
    }
    if (opt == -1) { cout << 0 << '\n'; exit(0); }

    vector<int> list;
    set<pli> ord;
    for (int j = 1; j <= n; j++) {
        int i = a[j].second;
        ord.insert({s[i], i});
        if (j != opt) continue;
        
        ldouble tar = m / a[j].first;
        ldouble sum = 0;
        for (auto it = ord.begin(); it != ord.end(); it++) {
            if (sum + it->first > tar) break;
            sum += it->first;
            list.push_back(it->second);
        }
        break; 
    }

    assert(ans.count == (int) list.size());
    cout << list.size() << '\n';
    for (int x : list) cout << x << '\n';
}

• Subtask 1: 23 / 30
• Subtask 2: 12 / 28
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 0 / 6
• Subtask 7: 0 / 6
• Subtask 8: 0 / 6
• Subtask 9: 0 / 6