Submission #509915

#	Time	Username	Problem	Language	Result	Execution time	Memory
509915		600Mihnea	Hiring (IOI09_hiring)	C++17	17 / 100	751 ms	40624 KiB

hiring

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Guy {
  int min_salary;
  int level;
  int ind;
};

struct Fraction {
  int x, y;
  Fraction(int x, int y) : x(x), y(y) {

  }
};

Fraction operator * (Fraction a, ll x) {
  a.x *= x;
  return a;
}

Fraction operator * (ll x, Fraction a) {
  a.x *= x;
  return a;
}


bool operator < (Fraction a, Fraction b) {
  return a.x * (ll) b.y < b.x * (ll) a.y;
}

bool operator > (Fraction a, Fraction b) {
  return a.x * (ll) b.y > b.x * (ll) a.y;
}

bool operator == (Fraction a, Fraction b) {
  return a.x * (ll) b.y == b.x * (ll) a.y;
}

bool operator < (Guy a, Guy b) {
  return Fraction(a.min_salary, a.level) < Fraction(b.min_salary, b.level);
}

const int N = (int) 5e5 + 7;
int n;
ll money;
Guy guys[N];

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

  ///freopen ("input", "r", stdin);

  cin >> n >> money;
  for (int i = 1; i <= n; i++) {
    cin >> guys[i].min_salary >> guys[i].level;
    guys[i].ind = i;
  }
  sort(guys + 1, guys + n + 1);

  multiset<pair<int, int>> mn;
  ll current_sum = 0;
  int print = 0;

  for (int i = 1; i <= n; i++) {
    current_sum += guys[i].level;
    mn.insert({guys[i].level, guys[i].ind});
    while (current_sum * Fraction(guys[i].min_salary, guys[i].level) > Fraction(money, 1)) {
      assert(!mn.empty());
      auto it = mn.end();
      it--;
      current_sum -= it->first;
      mn.erase(it);
    }
    if ((int) mn.size() > print) {
      print = (int) mn.size();
    }
  }
  mn.clear();
  current_sum = 0;
  for (int i = 1; i <= n; i++) {
    current_sum += guys[i].level;
    mn.insert({guys[i].level, guys[i].ind});
    while (current_sum * Fraction(guys[i].min_salary, guys[i].level) > Fraction(money, 1)) {
      assert(!mn.empty());
      auto it = mn.end();
      it--;
      current_sum -= it->first;
      mn.erase(it);
    }
    if ((int) mn.size() == print) {
      vector<int> sol;
      for (auto &it : mn) {
        sol.push_back(it.second);
      }
      sort(sol.begin(), sol.end());
      cout << (int) sol.size() << "\n";
      for (auto &i : sol) {
        cout << i << "\n";
      }
      exit(0);
    }
  }
  assert(0);

  return 0;
}

• Subtask 1: 7 / 30
• Subtask 2: 10 / 28
• Subtask 3: 0 / 6
• Subtask 4: 0 / 6
• Subtask 5: 0 / 6
• Subtask 6: 0 / 6
• Subtask 7: 0 / 6
• Subtask 8: 0 / 6
• Subtask 9: 0 / 6