oj.uz

Submission #574372

# Submission time Handle Problem Language Result Execution time Memory
574372 2022-06-08T12:41:02 Z mosiashvililuka Hiring (IOI09_hiring) C++14
100 / 100
 339 ms 30112 KB 
#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,W,seg[80009],seg2[80009],l,r,z,zz,za,L,pas1,pas2,pas3,I,PI,ans[500009],ansi;
pair <long long, long long> p[500009],P[500009];
pair <pair <long long, long long>, long long> pp[500009];
bool cmp(pair <long long, long long> q, pair <long long, long long> w){
    if(q.first*w.second<=w.first*q.second) return 0; else return 1;
}
bool CMP(pair <pair <long long, long long>, long long> q, pair <pair <long long, long long>, long long> w){
    if(q.first.first*w.first.second<=w.first.first*q.first.second) return 0; else return 1;
}
void read(long long q, long long w, long long rr){
    if(q==w){
        zx=L/q;zx=min(zx,seg2[rr]);
        z+=zx*q;
        zz+=zx;
        return;
    }
    if(seg[rr*2]>L){
        read(q,(q+w)/2,rr*2);
    }else{
        zz+=seg2[rr*2];z+=seg[rr*2];
        L-=seg[rr*2];
        read((q+w)/2+1,w,rr*2+1);
    }
}
void UP(long long rr, long long w){
    if(rr==0) return;
    seg[rr]+=w;seg2[rr]++;
    UP(rr/2,w);
}
void upd(long long q, long long w){
    UP(za+q-1,w);
}
int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>a>>W;
    for(i=1; i<=a; i++){
        cin>>p[i].first>>p[i].second;
        pp[i]={p[i],i};
    }
    za=1;
    while(za<20000) za*=2;
    sort(pp+1,pp+a+1,CMP);
    sort(p+1,p+a+1,cmp);
    for(i=a; i>=1; i--){
        z=0;zz=0;
        L=W*p[i].second/p[i].first;L-=p[i].second;
        if(L>=0) zz++;
        if(L>0) read(1,za,1);
        //cout<<i<<" "<<z<<" "<<zz<<"\n";
        if(pas1<zz){
            pas1=zz;
            zx=z+p[i].second;
            pas2=zx*p[i].first;pas3=p[i].second;
            I=i;
        }else{
            if(pas1==zz){
                zx=z+p[i].second;
                c=zx*p[i].first;d=p[i].second;
                if(c*pas3<pas2*d){
                    pas2=c;pas3=d;
                    I=i;
                }
            }
        }
        upd(p[i].second,p[i].second);
    }
    cout<<pas1<<"\n";
    for(i=I+1; i<=a; i++){
        PI++;P[PI]={p[i].second,pp[i].second};
    }
    sort(P+1,P+PI+1);
    for(i=1; i<pas1; i++){
        ansi++;ans[ansi]=P[i].second;
    }
    ansi++;ans[ansi]=pp[I].second;
    sort(ans,ans+ansi+1);
    for(i=1; i<=ansi; i++){
        cout<<ans[i]<<"\n";
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 3 ms 724 KB Output is correct
9 Correct 3 ms 1236 KB Output is correct
10 Correct 3 ms 1108 KB Output is correct
11 Correct 4 ms 1364 KB Output is correct
12 Correct 5 ms 976 KB Output is correct
13 Correct 5 ms 1492 KB Output is correct
14 Correct 7 ms 1748 KB Output is correct
15 Correct 8 ms 1844 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 12 ms 2132 KB Output is correct
5 Correct 27 ms 3468 KB Output is correct
6 Correct 185 ms 17444 KB Output is correct
7 Correct 225 ms 23912 KB Output is correct

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

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

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 7536 KB Output is correct
2 Correct 80 ms 7628 KB Output is correct
3 Correct 66 ms 7628 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 12560 KB Output is correct
2 Correct 112 ms 12688 KB Output is correct
3 Correct 110 ms 12724 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 26220 KB Output is correct
2 Correct 266 ms 26384 KB Output is correct
3 Correct 284 ms 26444 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 29884 KB Output is correct
2 Correct 325 ms 30112 KB Output is correct
3 Correct 318 ms 30080 KB Output is correct