oj.uz

Submission #320363

# Submission time Handle Problem Language Result Execution time Memory
320363 2020-11-08T11:02:42 Z AlexLuchianov Hiring (IOI09_hiring) C++14
100 / 100
 595 ms 20712 KB 
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <cmath>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

class FenwickTree{
private:
  std::vector<ll> aib;
  int n;
public:
  FenwickTree(int n_) {
    n = n_;
    aib.resize(1 + n);
  }
  void update(int pos, int val) {
    for(int x = pos; x <= n; x += (x ^ (x & (x - 1))))
      aib[x] += val;
  }
  ll query(int pos) {
    ll result = 0;
    for(int x = pos; 0 < x; x = (x & (x - 1)))
      result += aib[x];
    return result;
  }

  /*
    returns last x such that query(x) <= target
  */
  int lower_than(ll target) {
    int x = 0;
    for(int jump = (1 << 20); 0 < jump; jump /= 2) 
      if(x + jump <= n && aib[x + jump] <= target) {
        target -= aib[x + jump];
        x += jump;
      }
    return x;
  }
};

int const nmax = 500000;

struct Candidate{
  int salary;
  int qualification;
  int id;
  int real;
  bool operator < (Candidate const a) {
    return qualification < a.qualification;
  }
} v[1 + nmax];

bool compare(Candidate a, Candidate b) {
  return 1LL * a.salary * b.qualification < 1LL * b.salary * a.qualification;
}

int main() {
  int n;
  ll budget;
  std::cin >> n >> budget;
  for(int i = 1;i <= n; i++) { 
    std::cin >> v[i].salary >> v[i].qualification;
    v[i].real = i;
  }
  std::sort(v + 1, v + n + 1);
  for(int i = 1;i <= n; i++)
    v[i].id = i;
  std::sort(v + 1, v + n + 1, compare);
  FenwickTree aib(n), aibsum(n);
  
  int result = 0, eval = 0;
  double second_result = 0;

  for(int i = 1;i <= n; i++) {
    int id = v[i].id;
    aib.update(id, 1);
    aibsum.update(id, v[i].qualification);
    int target = aibsum.lower_than(budget * v[i].qualification / v[i].salary);
    int answer = aib.query(target);
    double answer2 = ((double)aibsum.query(target)) * v[i].salary / v[i].qualification;
    if(result < answer) {
      result = answer;
      eval = i;
      second_result = answer2;
    } else if(result == answer && answer2 < second_result) {
      second_result = answer2;
      eval = i;
    }
  }

  std::vector<std::pair<int,int>> sol;
  
  for(int i = 1; i <= eval; i++)
    sol.push_back({v[i].qualification, v[i].real});
  std::sort(sol.begin(), sol.end());
  std::cout << result;
  for(int i = 0; i < result; i++)
    std::cout << '\n' << sol[i].second;

  return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 3 ms 364 KB Output is correct
9 Correct 4 ms 492 KB Output is correct
10 Correct 5 ms 492 KB Output is correct
11 Correct 6 ms 620 KB Output is correct
12 Correct 8 ms 748 KB Output is correct
13 Correct 8 ms 620 KB Output is correct
14 Correct 12 ms 1004 KB Output is correct
15 Correct 14 ms 1004 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 19 ms 1132 KB Output is correct
5 Correct 60 ms 2660 KB Output is correct
6 Correct 346 ms 12244 KB Output is correct
7 Correct 457 ms 17176 KB Output is correct

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

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

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 5084 KB Output is correct
2 Correct 121 ms 5084 KB Output is correct
3 Correct 123 ms 5084 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 8848 KB Output is correct
2 Correct 195 ms 8792 KB Output is correct
3 Correct 197 ms 8828 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 488 ms 18716 KB Output is correct
2 Correct 481 ms 18644 KB Output is correct
3 Correct 517 ms 18788 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 20712 KB Output is correct
2 Correct 563 ms 20684 KB Output is correct
3 Correct 595 ms 20692 KB Output is correct