Submission #528366

#	Time	Username	Problem	Language	Result	Execution time	Memory
528366		cig32	Hiring (IOI09_hiring)	C++17	3 / 100	205 ms	20452 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;
  vector<double> v;
  for(int i=1; i<=n; i++) v.push_back(s[i] * 1.0 / q[i]);
  sort(v.begin(), v.end());
  f(v[v.size() - 1], 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);
} 
/*
6 69
4 1
1 2
2 6
9 4
7 3
12 73
*/

Compilation message (stderr)

hiring.cpp: In function 'void solve(long long int)':
hiring.cpp:46:7: warning: unused variable 'ans' [-Wunused-variable]
   46 |   int ans = -1;
      |       ^~~
hiring.cpp:47:10: warning: unused variable 'best' [-Wunused-variable]
   47 |   double best;
      |          ^~~~

• Subtask 1: 3 / 30
• Subtask 2: 0 / 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