Submission #228690

#	Time	Username	Problem	Language	Result	Execution time	Memory
228690		osaaateiasavtnl	Hiring (IOI09_hiring)	C++14	100 / 100	492 ms	58108 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) {
        /*
        used[posq[i]] = 1;
        */
        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;
        }

        /*
        int sum = 0, k = 0;
        for (int j = 1; j <= n; ++j) {
            if (used[j]) {
                sum += t[j - 1].f;
                ++k;

                if (sum * a[i].s <= W * a[i].q) {
                    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