제출 #509915

#제출 시각아이디문제언어결과실행 시간메모리
509915600MihneaHiring (IOI09_hiring)C++17
17 / 100
751 ms40624 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...