Submission #509924

#	Time	Username	Problem	Language	Result	Execution time	Memory
509924		600Mihnea	Hiring (IOI09_hiring)	C++17	100 / 100	535 ms	27632 KiB

hiring

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

struct Fraction {
  ll x, y;
  Fraction(ll x, ll 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 ll N = (ll) 5e5 + 7;
ll n;
ll money;
Guy guys[N];

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

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

  cin >> n >> money;
  for (ll 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<ll, ll>> mn;
  ll current_sum = 0;
  ll prll = 0;
  Fraction zda(0, 0);

  for (ll 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 ((ll) mn.size() > prll) {
      prll = (ll) mn.size();
      zda = current_sum * Fraction(guys[i].min_salary, guys[i].level);
    } else {
      if ((ll) mn.size() == prll) {
        if (current_sum * Fraction(guys[i].min_salary, guys[i].level) < zda) {
          zda = current_sum * Fraction(guys[i].min_salary, guys[i].level);
        }
      }
    }
  }
  mn.clear();
  current_sum = 0;
  for (ll 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 ((ll) mn.size() == prll && zda == current_sum * Fraction(guys[i].min_salary, guys[i].level)) {
      vector<ll> sol;
      for (auto &it : mn) {
        sol.push_back(it.second);
      }
      sort(sol.begin(), sol.end());
      cout << (ll) sol.size() << "\n";
      for (auto &i : sol) {
        cout << i << "\n";
      }
      exit(0);
    }
  }
  assert(0);

  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