oj.uz

Submission #297152

# Submission time Handle Problem Language Result Execution time Memory
297152 2020-09-11T10:02:46 Z Harry464 Hiring (IOI09_hiring) C++14
100 / 100
 1035 ms 32600 KB 
#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n;
  double w;
  cin >> n >> w;
  vector <pair<pair<double,int>,pair<double,double>>> c(n);
  for (int i = 0; i < n; i++){
    double p, q;
    cin >> p >> q;
    c[i] = make_pair(make_pair(p/q,i+1),make_pair(p,q));
  }
  sort(c.begin(),c.end());
  double totq = 0;
  priority_queue<double> kju;
  int najs = 0, ind;
  double najcijena = 1000000000;
  for (int i = 0; i < n; i++){
    kju.push(c[i].second.second);
    totq += c[i].second.second;
    double gran = w / c[i].first.first;
    while (totq > gran){
      totq -= kju.top();
      kju.pop();
    }
    double cijena = totq*c[i].first.first;
    if (kju.size() > najs || (kju.size() == najs && najcijena > cijena)){
      najs = kju.size();
      ind = i;
      najcijena = cijena;
    }
  }
  totq = 0;
  priority_queue<pair<double,int>> kju2;
  for (int i = 0; i <= ind; i++){
    kju2.push(make_pair(c[i].second.second,c[i].first.second));
    totq += c[i].second.second;
  }
  double gran = w / c[ind].first.first;
  while (totq > gran){
    totq -= kju2.top().first;
    kju2.pop();
  }
  cout << kju2.size() << endl;
  vector <int> rjesenje;
  while (!kju2.empty()){
    rjesenje.push_back(kju2.top().second);
    kju2.pop();
  }
  sort(rjesenje.begin(),rjesenje.end());
  for (int i = 0; i < rjesenje.size(); i++)
    cout << rjesenje[i] << endl;
}

Compilation message

hiring.cpp: In function 'int main()':
hiring.cpp:35:20: warning: comparison of integer expressions of different signedness: 'std::priority_queue<double>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |     if (kju.size() > najs || (kju.size() == najs && najcijena > cijena)){
      |         ~~~~~~~~~~~^~~~~~
hiring.cpp:35:42: warning: comparison of integer expressions of different signedness: 'std::priority_queue<double>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |     if (kju.size() > najs || (kju.size() == najs && najcijena > cijena)){
      |                               ~~~~~~~~~~~^~~~~~~
hiring.cpp:59:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   for (int i = 0; i < rjesenje.size(); i++)
      |                   ~~^~~~~~~~~~~~~~~~~
hiring.cpp:43:21: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   43 |   for (int i = 0; i <= ind; i++){
      |                   ~~^~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 4 ms 416 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 8 ms 640 KB Output is correct
10 Correct 9 ms 768 KB Output is correct
11 Correct 9 ms 896 KB Output is correct
12 Correct 18 ms 1024 KB Output is correct
13 Correct 9 ms 768 KB Output is correct
14 Correct 25 ms 1272 KB Output is correct
15 Correct 23 ms 1280 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 35 ms 1536 KB Output is correct
5 Correct 75 ms 3576 KB Output is correct
6 Correct 521 ms 18536 KB Output is correct
7 Correct 738 ms 26468 KB Output is correct

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

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

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 7664 KB Output is correct
2 Correct 204 ms 7664 KB Output is correct
3 Correct 203 ms 7664 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 13548 KB Output is correct
2 Correct 343 ms 13420 KB Output is correct
3 Correct 347 ms 13428 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 831 ms 29160 KB Output is correct
2 Correct 833 ms 28904 KB Output is correct
3 Correct 854 ms 28940 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 993 ms 32600 KB Output is correct
2 Correct 981 ms 32512 KB Output is correct
3 Correct 1035 ms 32488 KB Output is correct