oj.uz

Submission #963065

# Submission time Handle Problem Language Result Execution time Memory
963065 2024-04-14T12:47:44 Z hirayuu_oj Hiring (IOI09_hiring) C++17
100 / 100
 393 ms 29264 KB 
#include<bits/stdc++.h>
#include <tuple>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
using ld=long double;

template<class S>
struct fw_tree{
    int size;
    vector<S> tree;
    fw_tree(int sz){
        size=sz;
        tree=vector<S>(sz+1,0);
    }
    void add(int p,int v){
        p++;
        while(p<=size){
            tree[p]+=v;
            p+=p&-p;
        }
    }
    S sum(int r){
        S ret=0;
        while(r>0){
            ret+=tree[r];
            r-=r&-r;
        }
        return ret;
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    ll W;
    cin>>N>>W;
    vector<tuple<int,int,int>> work(N);
    rep(i,N){
        int S,Q;
        cin>>S>>Q;
        work[i]={Q,S,i};
    }
    sort(all(work));
    vector<pair<ld,int>> order(N);
    rep(i,N){
        order[i]={((ld)get<1>(work[i]))/((ld)get<0>(work[i])),i};
    }
    sort(all(order));
    fw_tree<ll> cost(N);
    fw_tree<int> count(N);
    pair<int,ld> ans={-1,0};
    pair<int,int> out={-1,-1};
    rep(i,N){
        ll q,s;
        tie(q,s,ignore)=work[order[i].second];
        count.add(order[i].second,1);
        cost.add(order[i].second,q);
        int ok=0,ng=N+1;
        while(ng-ok>1){
            int mid=(ok+ng)>>1;
            if(cost.sum(mid)*s<=W*q){
                ok=mid;
            }
            else{
                ng=mid;
            }
        }
        int now=count.sum(ok);
        ld cst=cost.sum(ok)*order[i].first;
        if(ans<pair(now,-cst)){
            ans=pair(now,-cst);
            out=pair(i,ok);
        }
    }
    cout<<ans.first<<"\n";
    vector<bool> col(N,0);
    rep(i,out.first+1){
        col[order[i].second]=1;
    }
    rep(i,out.second){
        if(col[i]){
            cout<<get<2>(work[i])+1<<"\n";
        }
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 472 KB Output is correct
7 Correct 2 ms 344 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 3 ms 604 KB Output is correct
11 Correct 4 ms 604 KB Output is correct
12 Correct 5 ms 860 KB Output is correct
13 Correct 5 ms 860 KB Output is correct
14 Correct 7 ms 1364 KB Output is correct
15 Correct 8 ms 1116 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 11 ms 1372 KB Output is correct
5 Correct 41 ms 4276 KB Output is correct
6 Correct 216 ms 17548 KB Output is correct
7 Correct 288 ms 23392 KB Output is correct

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

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

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 6716 KB Output is correct
2 Correct 75 ms 6860 KB Output is correct
3 Correct 74 ms 6736 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 11848 KB Output is correct
2 Correct 128 ms 11876 KB Output is correct
3 Correct 128 ms 11860 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 26212 KB Output is correct
2 Correct 345 ms 26208 KB Output is correct
3 Correct 359 ms 26132 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 29124 KB Output is correct
2 Correct 393 ms 29264 KB Output is correct
3 Correct 389 ms 29128 KB Output is correct