제출 #528349

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
528349		cig32	Hiring (IOI09_hiring)	C++17	8 / 100	1588 ms	16848 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) {
    if(f(i, 0) > ans) {
      ans = f(i, 0);
      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);
} 
/*
12 11
1 2
1 2
4 3
2 3
1 3
5 1
4 6
6 4
9 10
10 11
11 12
3
9 12
12 9
5 6
*/

컴파일 시 표준 에러 (stderr) 메시지

hiring.cpp: In function 'void solve(long long int)':
hiring.cpp:54:4: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |   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