oj.uz

Submission #228691

# Submission time Handle Problem Language Result Execution time Memory
228691 2020-05-02T11:01:50 Z osaaateiasavtnl Hiring (IOI09_hiring) C++14
100 / 100
 530 ms 52688 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 512 KB Output is correct
7 Correct 6 ms 640 KB Output is correct
8 Correct 6 ms 640 KB Output is correct
9 Correct 8 ms 1024 KB Output is correct
10 Correct 8 ms 1024 KB Output is correct
11 Correct 9 ms 1152 KB Output is correct
12 Correct 10 ms 1280 KB Output is correct
13 Correct 11 ms 1408 KB Output is correct
14 Correct 14 ms 1920 KB Output is correct
15 Correct 15 ms 1920 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 19 ms 2684 KB Output is correct
5 Correct 45 ms 8172 KB Output is correct
6 Correct 302 ms 38924 KB Output is correct
7 Correct 329 ms 47956 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 12904 KB Output is correct
2 Correct 109 ms 12904 KB Output is correct
3 Correct 105 ms 12908 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 24160 KB Output is correct
2 Correct 167 ms 24284 KB Output is correct
3 Correct 183 ms 24160 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 50260 KB Output is correct
2 Correct 435 ms 50392 KB Output is correct
3 Correct 414 ms 50260 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 490 ms 52604 KB Output is correct
2 Correct 530 ms 52560 KB Output is correct
3 Correct 508 ms 52688 KB Output is correct