Submission #320363

#	Time	Username	Problem	Language	Result	Execution time	Memory
320363		AlexLuchianov	Hiring (IOI09_hiring)	C++14	100 / 100	595 ms	20712 KiB

hiring

#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 / 30
• Subtask 2: 28 / 28
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 6 / 6
• Subtask 7: 6 / 6
• Subtask 8: 6 / 6
• Subtask 9: 6 / 6