Submission #228691

#	Time	Username	Problem	Language	Result	Execution time	Memory
228691		osaaateiasavtnl	Hiring (IOI09_hiring)	C++14	100 / 100	530 ms	52688 KiB

hiring

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
const int N = 5e5 + 7;
int n, W;
struct Chel {
    int s, q, i;
} a[N];  
bool comp(Chel a, Chel b) {
    //return (a.s/a.q) < (b.s/b.q);
    return a.s * b.q < b.s * a.q;
}   
bool compq(int i, int j) {
    return a[i].q < a[j].q;
}   
bool ls(ii a, ii b) {
    return a.f * b.s < b.f * a.s;
}
struct Tree {
int cnt[N << 2], sum[N << 2];
void relax(int v) {
    sum[v] = sum[v * 2 + 1] + sum[v * 2 + 2];
    cnt[v] = cnt[v * 2 + 1] + cnt[v * 2 + 2];
}   
void add(int v, int tl, int tr, int p, int x) {
    if (tl == tr) {
        sum[v] += x;
        ++cnt[v];
        return;
    }
    int tm = (tl + tr) >> 1;
    if (p <= tm)
        add(v * 2 + 1, tl, tm, p, x);
    else
        add(v * 2 + 2, tm + 1, tr, p, x);
    relax(v);                                     
}   
ii get(int v, int tl, int tr, int W, int f) {
    if (tl == tr) {
        if (sum[v] * f > W)
            return mp(0, 0);
        else
            return mp(sum[v], cnt[v]);
    }   
    int tm = (tl + tr) >> 1;
    if (sum[v * 2 + 1] * f >= W) {
        return get(v * 2 + 1, tl, tm, W, f);
    }
    else {
        W -= sum[v * 2 + 1] * f;
        ii ans = get(v * 2 + 2, tm + 1, tr, W, f);
        ans.f += sum[v * 2 + 1];
        ans.s += cnt[v * 2 + 1];
        return ans;
    }                       
}   
} d;
int posq[N];
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n >> W;
    for (int i = 0; i < n; ++i) {
        cin >> a[i].s >> a[i].q;
        a[i].i = i;
    }   
    sort(a, a + n, comp);
    vector <ii> t;
    for (int i = 0; i < n; ++i)
        t.app(mp(a[i].q, i));
    sort(all(t));
    for (int i = 0; i < n; ++i)
        posq[t[i].s] = i + 1;
    int ans = 0;
    ii pay = {0, 1};
    int ans_i = -1;
    for (int i = 0; i < n; ++i) {
        d.add(0, 0, n, posq[i], a[i].q);
        int sum, k;
        tie(sum, k) = d.get(0, 0, n, W * a[i].q, a[i].s);
        ii np = mp(sum * a[i].s, a[i].q);
        if (k > ans || (k == ans && ls(np, pay))) {
            ans = k;
            pay = np;
            ans_i = i;
        }
    }
    cout << ans << endl;
    if (ans > 0) {
        vector <ii> t;
        for (int i = 0; i <= ans_i; ++i) {
            t.app(mp(a[i].q, a[i].i));
        }       
        sort(all(t));
        for (int i = 0; i < ans; ++i)
            cout << t[i].s + 1 << ' ';
        cout << endl;           
    }   
}

• 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