Submission #528361

#	Time	Username	Problem	Language	Result	Execution time	Memory
528361		cig32	Hiring (IOI09_hiring)	C++17	8 / 100	1599 ms	20144 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(double i=0.005; i<=w; i+=0.005) {
    int ok = f(i, 0);
    if(ok > ans) {
      ans = ok;
      best = i;
    }
    else if(ok == ans) {
      if(i < best) {
        best = 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: 6 / 30
• Subtask 2: 2 / 28
• Subtask 3: 0 / 6
• Subtask 4: 0 / 6
• Subtask 5: 0 / 6
• Subtask 6: 0 / 6
• Subtask 7: 0 / 6
• Subtask 8: 0 / 6
• Subtask 9: 0 / 6