oj.uz

Submission #415288

# Submission time Handle Problem Language Result Execution time Memory
415288 2021-05-31T20:00:31 Z Antekb Hiring (IOI09_hiring) C++14
100 / 100
 921 ms 34456 KB 
#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
typedef long double ld;
int main(){
    int n;
    long long w;
    cin>>n>>w;
    vector<pair<pair<ld, int >, pair<int, int> > > V;
    for(int i=0; i<n; i++){
        int a, b;
        cin>>a>>b;
        V.push_back({{a/ld(b), a},  {b, i}});
    }
    sort(V.begin(), V.end());
    set<pair<int, int> > S;
    long long sum=0;
    int l=0;
    long double k=0;
    for(int i=0; i<n; i++){
        S.insert(V[i].nd);
        sum+=V[i].nd.st;
        /*while(S.size()&& S2.size() && *S2.begin()<*S.crbegin()){
            sum-=(*S.crbegin()).st;
            sum+=(*S.crbegin()).st;
            S.insert(*S2.begin());
            S2.erase(*S2.begin());

        }*/
        while(S.size() && sum*V[i].st.nd>w*V[i].nd.st){
            sum-=(*S.crbegin()).st;
            S.erase(S.find(*S.crbegin()));
        }
        if(S.size()>l){
            l=S.size();
            k=sum*V[i].st.nd/ld(V[i].nd.st);
        }
        else if(S.size()== l) k =min(k, sum*V[i].st.nd/ld(V[i].nd.st));
    }
    cout<<l<<"\n";
    S.clear();
    sum=0;
    for(int i=0; i<n; i++){
        S.insert(V[i].nd);
        sum+=V[i].nd.st;
        while(S.size() && sum*V[i].st.nd>w*V[i].nd.st){
            sum-=(*S.crbegin()).st;
            S.erase(S.find(*S.crbegin()));
        }
        if(S.size()==l && k==sum*V[i].st.nd/ld(V[i].nd.st)){
            for(auto j:S)cout<<j.nd+1<<"\n";
            return 0;
        }
    }
    //cout<<"a";
}

Compilation message

hiring.cpp: In function 'int main()':
hiring.cpp:35:20: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |         if(S.size()>l){
      |            ~~~~~~~~^~
hiring.cpp:39:25: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |         else if(S.size()== l) k =min(k, sum*V[i].st.nd/ld(V[i].nd.st));
      |                 ~~~~~~~~^~~~
hiring.cpp:51:20: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |         if(S.size()==l && k==sum*V[i].st.nd/ld(V[i].nd.st)){
      |            ~~~~~~~~^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 3 ms 448 KB Output is correct
7 Correct 3 ms 460 KB Output is correct
8 Correct 4 ms 588 KB Output is correct
9 Correct 6 ms 780 KB Output is correct
10 Correct 7 ms 780 KB Output is correct
11 Correct 7 ms 696 KB Output is correct
12 Correct 11 ms 960 KB Output is correct
13 Correct 10 ms 1096 KB Output is correct
14 Correct 21 ms 1096 KB Output is correct
15 Correct 19 ms 1220 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 24 ms 1860 KB Output is correct
5 Correct 65 ms 6520 KB Output is correct
6 Correct 465 ms 24912 KB Output is correct
7 Correct 662 ms 27040 KB Output is correct

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

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

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 7652 KB Output is correct
2 Correct 177 ms 7652 KB Output is correct
3 Correct 165 ms 7660 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 13312 KB Output is correct
2 Correct 242 ms 13388 KB Output is correct
3 Correct 242 ms 13504 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 716 ms 30052 KB Output is correct
2 Correct 712 ms 29964 KB Output is correct
3 Correct 670 ms 30056 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 910 ms 34448 KB Output is correct
2 Correct 921 ms 34444 KB Output is correct
3 Correct 892 ms 34456 KB Output is correct