제출 #1166952

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166952		julia_08	Hiring (IOI09_hiring)	C++20	80 / 100	1597 ms	17956 KiB

hiring

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int MAXN = 5e5 + 10;

struct worker{
  int s, q, id;

  bool operator < (worker b){
    if((ll) s * b.q != (ll) b.s * q) return (ll) s * b.q < (ll) b.s * q;
    return id < b.id;
  }

};

worker a[MAXN];

int n; ll w;

ll num, den;

int id;

bool check(int k){

  set<pair<int, int>> s;

  ll sum = 0;

  for(int i=1; i<k; i++){
    s.insert({a[i].q, a[i].id});
    sum += a[i].q;
  }

  num = 1e18, den = 1;

  for(int i=k; i<=n; i++){

    ll cur_num = a[i].s * (sum + a[i].q), cur_den = a[i].q;

    if(cur_num * den < num * cur_den){
      num = cur_num, den = cur_den;
      id = i;
    }

    if(a[i].q < (*s.rbegin()).first){
      sum -= (*s.rbegin()).first;
      s.erase(*s.rbegin());

      s.insert({a[i].q, a[i].id});
      sum += a[i].q;
    }

  }

  return num <= w * den;
}

int bs(){

  int l = 0, r = n;

  while(l < r){
    int m = l + (r - l + 1) / 2;
    if(check(m)) l = m;
    else r = m - 1;
  }

  check(l);

  return l;
}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> w;

  for(int i=1; i<=n; i++){
    cin >> a[i].s >> a[i].q;
    a[i].id = i;
  }

  sort(a + 1, a + n + 1);

  int k = bs();

  vector<pair<int, int>> workers;

  for(int i=1; i<id; i++){
    workers.push_back({a[i].q, a[i].id});
  }

  sort(workers.begin(), workers.end());

  cout << k << "\n";

  cout << a[id].id << "\n";

  for(int i=0; i<k-1; i++) cout << workers[i].second << "\n";

  return 0;
}

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