Submission #528353

#	Time	Username	Problem	Language	Result	Execution time	Memory
528353		cig32	Hiring (IOI09_hiring)	C++17	32 / 100	1599 ms	24028 KiB

hiring

#include "bits/stdc++.h"
using namespace std;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 5e5 + 10;
const int MOD = 1e9 + 7;
#define int long long
 
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int n;
int s[MAXN], q[MAXN], w;
int f(double F, bool output) { // number of workers hirable
  vector<pair<double, int> > v;
  for(int i=1; i<=n; i++) {
    if(q[i] * F + 1e-10 >= s[i]) {
      v.push_back({q[i] * F, i});
    }
  }
  sort(v.begin(), v.end());
  double o = 0;
  int cnt = 0;
  vector<int> r;
  for(pair<double, int> y: v) {
    double x = y.first;
    if(o + x <= w + 1e-10) {
      o += x;
      cnt++;
      r.push_back(y.second);
    }
    else {
      break;
    }
  }
  if(output) {
    cout << cnt << "\n";
    for(int x: r)cout << x << "\n";
  }
  return cnt;
}
void solve(int tc) {
  cin >> n >> w;
  for(int i=1; i<=n; i++) cin >> s[i] >> q[i];
  int sum = 0;
  for(int i=1; i<=n; i++) sum += q[i];
  int ans = -1;
  double best;
  for(int i=1; i<=n; i++) {
    double ok = f(s[i] * 1.0 / q[i], 0);
    if(ok > ans) {
      ans = ok;
      best = s[i] * 1.0 / q[i];
    }
    else if(abs(ok - ans) <= 1e-10) {
      if(s[i] * 1.0 / q[i] < best) {
        best = s[i] * 1.0 / q[i];
      }
    }
  }
  f(best, 1);
}

int32_t main(){
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1;// cin >> t;
  for(int i=1; i<=t; i++) solve(i);
} 

Compilation message (stderr)

hiring.cpp: In function 'void solve(long long int)':
hiring.cpp:60:4: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
   60 |   f(best, 1);
      |   ~^~~~~~~~~

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