oj.uz

Submission #906493

# Submission time Handle Problem Language Result Execution time Memory
906493 2024-01-14T11:01:45 Z JakobZorz Hiring (IOI09_hiring) C++17
53 / 100
 1500 ms 17892 KB 
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<limits.h>
#include<math.h>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<iomanip>
#include<cstring>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
//const int MOD=1e9+7;
//typedef pair<ll,ll>Point;
//typedef pair<ll,ll>Line;
//#define x first
//#define y second
 
struct Obj{
    ll s; // min salary
    ll q; // skill
    int i;
};
 
bool cmp(Obj&a,Obj&b){
    return a.s*b.q<b.s*a.q;
}

ll w;
int n;
ll vals[500000];
int present[500000];
void add(ll val){
    /*vals.push_back(val);
    sort(vals.begin(),vals.end());*/
    int l=0,r=n;
    while(l<r-1){
        int m=(l+r)/2;
        if(vals[m]>val||(vals[m]==val&&present[m]))
            r=m;
        else
            l=m;
    }
    present[l]=1;
}

int get(ll&cost,ll m1,ll m2){
    int cres=0;
    int res=0;
    while(cres<n){
        if((cost+vals[cres])*m1<=w*m2){
            cost+=vals[cres]*present[cres];
            res+=present[cres];
            cres++;
        }else{
            break;
        }
    }
    return res;
}

void solve(){
    cin>>n>>w;
    vector<Obj>arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i].s>>arr[i].q;
        arr[i].i=i+1;
        vals[i]=arr[i].q;
    }
    sort(vals,vals+n);
    sort(arr.begin(),arr.end(),cmp);
    int res=0;
    int opt=0;
    ll m1=0,m2=1; // spends m1/m2
    for(int i=0;i<n;i++){
        if(i)
            add(arr[i-1].q);
        
        ll cost=arr[i].q;
        if(cost*arr[i].s>w*arr[i].q)
            continue;
        
        int cres=get(cost,arr[i].s,arr[i].q);
        
        if(cres+1>res){
            res=cres+1;
            opt=i;
            m1=cost*arr[i].s;
            m2=arr[i].q;
        }else if(cres+1==res){
            if((__int128)cost*arr[i].s*m2<(__int128)m1*arr[i].q){
                opt=i;
                m1=cost;
                m2=arr[i].q;
            }
        }
    }
    
    
    cout<<res<<"\n";
    if(res){
        cout<<arr[opt].i<<"\n";
        int i=opt;
        vector<pair<ll,int>>vals;
        for(int j=0;j<i;j++)
            vals.emplace_back(arr[j].q,arr[j].i);
        sort(vals.begin(),vals.end());
        ll cost=arr[i].q;
        int cres=0;
        while(cres<(int)vals.size()){
            if((cost+vals[cres].first)*arr[i].s<=w*arr[i].q){
                cost+=vals[cres].first;
                cout<<vals[cres].second<<"\n";
                cres++;
            }else{
                break;
            }
        }
    }
}
 
int main(){
    ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
    //freopen("bank.in","r",stdin);freopen("bank.out","w",stdout);
    int t=1;//cin>>t;
    while(t--)solve();
    return 0;
}
 
/*
 
4 100
5 1000
10 100
8 10
20 1
 
2
2
3
 
3 4
1 2
1 3
1 3
 
3
1
2
3
 
 
3 40
10 1
10 2
10 3
 
2
2
3
 
 
5 30
1 1
2 2
4 4
8 8
16 16
 
4
1
2
3
4
 
2 2
2 2
1 1

1
2
 
6 5
1 96
2 100
2 97
3 95
4 98
5 99
 
2
1
2
 
 */

Subtask #1
26.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Partially correct 1 ms 2396 KB Partially correct
6 Correct 3 ms 2396 KB Output is correct
7 Partially correct 4 ms 2396 KB Partially correct
8 Correct 6 ms 2564 KB Output is correct
9 Correct 18 ms 2648 KB Output is correct
10 Correct 20 ms 2640 KB Output is correct
11 Correct 15 ms 2908 KB Output is correct
12 Correct 60 ms 3148 KB Output is correct
13 Partially correct 42 ms 2652 KB Partially correct
14 Correct 119 ms 3112 KB Output is correct
15 Partially correct 151 ms 3168 KB Partially correct

Subtask #2
12.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Partially correct 1 ms 2396 KB Partially correct
3 Correct 1 ms 2396 KB Output is correct
4 Partially correct 293 ms 3308 KB Partially correct
5 Execution timed out 1535 ms 6424 KB Time limit exceeded
6 Execution timed out 1539 ms 11704 KB Time limit exceeded
7 Execution timed out 1532 ms 14880 KB Time limit exceeded

Subtask #3
3.0 / 6.0

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

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

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

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1548 ms 7524 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1520 ms 9536 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1515 ms 16580 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1540 ms 17892 KB Time limit exceeded
2 Halted 0 ms 0 KB -