oj.uz

답안 #963060

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
963060 2024-04-14T12:40:01 Z hirayuu_oj Hiring (IOI09_hiring) C++17
50 / 100
 377 ms 32564 KB 
#include<bits/stdc++.h>
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<pair<int,int>> work(N);
    rep(i,N){
        int S,Q;
        cin>>S>>Q;
        work[i]={Q,S};
    }
    sort(all(work));
    vector<pair<ld,int>> order(N);
    rep(i,N){
        order[i]={((ld)work[i].second)/((ld)work[i].first),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)=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<<i+1<<"\n";
        }
    }
}

Subtask #1
15.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 0 ms 348 KB Partially correct
2 Partially correct 0 ms 344 KB Partially correct
3 Partially correct 0 ms 348 KB Partially correct
4 Partially correct 0 ms 348 KB Partially correct
5 Partially correct 1 ms 348 KB Partially correct
6 Partially correct 1 ms 348 KB Partially correct
7 Partially correct 2 ms 344 KB Partially correct
8 Partially correct 2 ms 604 KB Partially correct
9 Partially correct 3 ms 604 KB Partially correct
10 Partially correct 3 ms 604 KB Partially correct
11 Partially correct 3 ms 604 KB Partially correct
12 Partially correct 4 ms 856 KB Partially correct
13 Partially correct 5 ms 1116 KB Partially correct
14 Partially correct 8 ms 1120 KB Partially correct
15 Partially correct 8 ms 1412 KB Partially correct

Subtask #2
14.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 348 KB Partially correct
2 Partially correct 0 ms 356 KB Partially correct
3 Partially correct 1 ms 356 KB Partially correct
4 Partially correct 12 ms 1628 KB Partially correct
5 Partially correct 34 ms 4300 KB Partially correct
6 Partially correct 245 ms 19420 KB Partially correct
7 Partially correct 280 ms 25840 KB Partially correct

Subtask #3
3.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 348 KB Partially correct
2 Partially correct 1 ms 348 KB Partially correct
3 Partially correct 1 ms 344 KB Partially correct

Subtask #4
3.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 348 KB Partially correct
2 Partially correct 1 ms 348 KB Partially correct
3 Partially correct 1 ms 500 KB Partially correct

Subtask #5
3.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 348 KB Partially correct
2 Partially correct 1 ms 352 KB Partially correct
3 Partially correct 1 ms 344 KB Partially correct

Subtask #6
3.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 77 ms 7504 KB Partially correct
2 Partially correct 74 ms 7504 KB Partially correct
3 Partially correct 82 ms 7668 KB Partially correct

Subtask #7
3.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 135 ms 12884 KB Partially correct
2 Partially correct 131 ms 13000 KB Partially correct
3 Partially correct 131 ms 12940 KB Partially correct

Subtask #8
3.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 332 ms 29232 KB Partially correct
2 Partially correct 326 ms 29268 KB Partially correct
3 Partially correct 326 ms 29232 KB Partially correct

Subtask #9
3.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 372 ms 32564 KB Partially correct
2 Partially correct 367 ms 32384 KB Partially correct
3 Partially correct 377 ms 32432 KB Partially correct