oj.uz

Submission #480554

# Submission time Handle Problem Language Result Execution time Memory
480554 2021-10-17T03:09:48 Z definitelynotmee Hiring (IOI09_hiring) C++
100 / 100
 846 ms 48392 KB 
#include<bits/stdc++.h>
#define mp make_pair
#define mt make_tuple
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
using namespace std;
template <typename T>
using matrix = vector<vector<T>>;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const double EPS = 1e-7;
const int MOD = 1e9 + 7;
const int MAXN = 1e6+1;

inline int midpoint(int l, int r){
    return (l+r)>>1;
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, w;
    cin >> n >> w;
    vector<pll> v(n);
    vector<int> o(n), o1(n),o2(n);

    for(int i = 0; i < n; i++){
        cin >> v[i].ff >> v[i].ss;
    } 
    iota(all(o1),0);
    sort(all(o1),[&](int a,int b){
        if(v[a].ss == v[b].ss)
            return v[a].ff < v[b].ff;
        return v[a].ss < v[b].ss;
    });
    for(int i = 0; i < n; i++){
        o2[o1[i]] = i;
    }
    iota(all(o),0);
    sort(all(o),[&](int a, int b){
        if(v[a].ff*v[b].ss == v[a].ss*v[b].ff)
            return o2[a] < o2[b];
        return v[a].ff*v[b].ss < v[a].ss*v[b].ff;
    });

    vector<pll> tree(4*n);
    function<void(int,int,int,int,int)> update= [&](int id, int l, int r, int q, int val){
        if(l > q || r < q)
            return;
        if(l == r && r == q){
            tree[id] = {val,1};
            return;
        }
        int e = id*2+1;
        int d = id*2+2;
        int m = midpoint(l,r);
        update(e,l,m,q,val);
        update(d,m+1,r,q,val);
        tree[id] = {tree[e].ff + tree[d].ff, tree[e].ss + tree[d].ss};
    };
    struct fraction{
        ll x,y;
        bool operator<(fraction b){
            return x*b.y < y*b.x;
        }
    };
    fraction sobra = {0,1};
    function<int(int,int,int,ll,ll)> bb =[&](int id,int l, int r, ll rest, ll cost)->int{
        if(l==r){
            if(tree[id].ss && tree[id].ff*cost <= rest){
                sobra.x = rest-tree[id].ff*cost;
                return 1;
            }
            sobra.x = rest;
            return 0;
        }
            
        int e = id*2+1;
        int d = id*2+2;
        int m = midpoint(l,r);
        if(tree[e].ff*cost < rest)
            return bb(d,m+1,r,rest-tree[e].ff*cost,cost)+tree[e].ss;
        return bb(e,l,m,rest,cost);
    };
    pair<int,fraction> resp = {0,{0,1}};
    int respid = 0;
    for(int i = 0; i < n; i++){
        update(0,0,n-1,o2[o[i]],v[o[i]].ss);
        int cur = bb(0,0,n-1,w*v[o[i]].ss,v[o[i]].ff);
        sobra.y = v[o[i]].ss;

        if(resp.ff < cur || (resp.ff == cur && resp.ss < sobra)){
            resp = {cur,sobra},respid = i;
        }
    }
    cout << resp.ff << '\n';
    vector<int> in;
    for(int i = 0; i <= respid; i++){
        in.push_back(o[i]);
    }
    sort(all(in),[&](int a,int b){
        return o2[a] < o2[b];
    });
    for(int i = 0; i < resp.ff; i++){
        cout << in[i] + 1<< '\n';
    }
    return 0;

}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 3 ms 492 KB Output is correct
8 Correct 3 ms 460 KB Output is correct
9 Correct 4 ms 716 KB Output is correct
10 Correct 5 ms 716 KB Output is correct
11 Correct 6 ms 916 KB Output is correct
12 Correct 7 ms 1100 KB Output is correct
13 Correct 8 ms 1100 KB Output is correct
14 Correct 12 ms 1592 KB Output is correct
15 Correct 15 ms 1680 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 21 ms 2240 KB Output is correct
5 Correct 93 ms 6468 KB Output is correct
6 Correct 504 ms 29000 KB Output is correct
7 Correct 566 ms 38652 KB Output is correct

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

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

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 11192 KB Output is correct
2 Correct 160 ms 11164 KB Output is correct
3 Correct 175 ms 11208 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 19528 KB Output is correct
2 Correct 323 ms 19600 KB Output is correct
3 Correct 267 ms 19652 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 662 ms 43248 KB Output is correct
2 Correct 659 ms 43368 KB Output is correct
3 Correct 671 ms 43292 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 846 ms 48392 KB Output is correct
2 Correct 781 ms 48308 KB Output is correct
3 Correct 771 ms 48336 KB Output is correct