oj.uz

Submission #752111

# Submission time Handle Problem Language Result Execution time Memory
752111 2023-06-02T10:09:04 Z DJeniUp Hiring (IOI09_hiring) C++17
100 / 100
 716 ms 59120 KB 
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pairll;
typedef pair<ll,ull>pairull;
typedef pair<ll,pairll>pair3l;
typedef long double ld;
typedef pair<ld,ll>pairld;

#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define N 100007
//#define MOD 998244353
#define INF 1000007
#define eps 0.0000000001

ll n;

ld k,a[5*N],b[5*N],sm[2*N];

struct D{
    ll n;
    
    ld a,b;
}d[5*N];

bool mcp(D d1, D d2){
    if(d1.a*d2.b!=d2.a*d1.b)return d1.a*d2.b<d2.a*d1.b;
    else return d1.b<d2.b;
}

bool mcp1(D d1, D d2){
    return d1.n<d2.n;
}

priority_queue<pairld>q;

priority_queue<ll,vector<ll>, greater<ll> >rs;

int main(){
    
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
        d[i].n=i;
        d[i].a=a[i];
        d[i].b=b[i];
    }
    sort(d+1,d+1+n,mcp);
    ll res=0;
    ld x=0;
    ld y=0;
    ll h=0;
    ll j=0;
    for(int i=1;i<=n;i++){
        x=max(x,d[i].a/d[i].b);
        y+=d[i].b;
        q.push({d[i].b,d[i].n});
        h++;
        while(x*y>k+eps){
            y-=q.top().fr;
            q.pop();
            h--;
        }
        sm[i]=x*y;
        if(h>res+eps){
            res=h;
            j=i;
        }else if(h==res){
            if(sm[j]>x*y+eps){
                j=i;
            }
        }
    }
    //cout<<j<<" "<<res<<endl;
    while(q.size()>0){
        q.pop();
    }
    x=0;
    y=0;
    for(int i=1;i<=j;i++){
        x=max(x,d[i].a/d[i].b);
        y+=d[i].b;
        q.push({d[i].b,d[i].n});
        while(x*y>k){
            y-=q.top().fr;
            q.pop();
        }
        
    }
    while(q.size()>0){
        rs.push(q.top().sc);
        q.pop();
    }
    cout<<rs.size()<<endl;
    while(rs.size()>0){
        cout<<rs.top()<<endl;
        rs.pop();
    }

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 7 ms 852 KB Output is correct
10 Correct 6 ms 980 KB Output is correct
11 Correct 7 ms 976 KB Output is correct
12 Correct 10 ms 1492 KB Output is correct
13 Correct 9 ms 1364 KB Output is correct
14 Correct 15 ms 2008 KB Output is correct
15 Correct 18 ms 2196 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 24 ms 2768 KB Output is correct
5 Correct 68 ms 7824 KB Output is correct
6 Correct 401 ms 35704 KB Output is correct
7 Correct 527 ms 47724 KB Output is correct

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

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

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 14512 KB Output is correct
2 Correct 156 ms 14492 KB Output is correct
3 Correct 180 ms 14440 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 25328 KB Output is correct
2 Correct 245 ms 25400 KB Output is correct
3 Correct 261 ms 25424 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 650 ms 52936 KB Output is correct
2 Correct 610 ms 52980 KB Output is correct
3 Correct 627 ms 52904 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 714 ms 59120 KB Output is correct
2 Correct 716 ms 59108 KB Output is correct
3 Correct 688 ms 59056 KB Output is correct