oj.uz

Submission #509924

# Submission time Handle Problem Language Result Execution time Memory
509924 2022-01-14T12:03:31 Z 600Mihnea Hiring (IOI09_hiring) C++17
100 / 100
 535 ms 27632 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 5 ms 624 KB Output is correct
11 Correct 4 ms 460 KB Output is correct
12 Correct 4 ms 844 KB Output is correct
13 Correct 3 ms 588 KB Output is correct
14 Correct 7 ms 972 KB Output is correct
15 Correct 8 ms 1056 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 11 ms 1356 KB Output is correct
5 Correct 30 ms 2808 KB Output is correct
6 Correct 249 ms 15136 KB Output is correct
7 Correct 420 ms 21488 KB Output is correct

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

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

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 6108 KB Output is correct
2 Correct 93 ms 6176 KB Output is correct
3 Correct 85 ms 6104 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 10540 KB Output is correct
2 Correct 110 ms 10496 KB Output is correct
3 Correct 114 ms 10528 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 23300 KB Output is correct
2 Correct 405 ms 23272 KB Output is correct
3 Correct 417 ms 23424 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 27524 KB Output is correct
2 Correct 526 ms 27612 KB Output is correct
3 Correct 531 ms 27632 KB Output is correct