B.cc

#include <cassert>

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

const int MAXN = 100005, MAXK = 1005;
const int ITER = 100;
int N, K, H;

struct Lemming {
  public:
    Lemming() : m(0), v(0), idx(-1), k(m, v) {}
    Lemming(int m, int v, int idx) : m(m), v(v), idx(idx), k(m, v) {}
    bool operator<(Lemming const& o) const {
      return k < o.k;
    }
    int m, v;
    int idx;
  private:
    pair<int, int> k;
};

int m[MAXN], v[MAXN];
Lemming lem[MAXN];
int sol[MAXK];

bool check(long double t) {
  int i = 0, j = 0, ht = H;
  while (i < N && j < K) {
    if (ht <= t * lem[i].v) {
      ht += H;
      sol[j] = lem[i].idx;
      ++j;
    }
    ++i;
  }
  return j == K;
}

int main() {
  ios_base::sync_with_stdio(false);

  cin >> N >> K >> H;

  int i;
  for (i = 0; i < N; ++i)
    cin >> m[i];
  for (i = 0; i < N; ++i) {
    cin >> v[i];
    lem[i] = Lemming(m[i], v[i], i);
  }
  sort(lem, lem + N);
  vector<int> m1(m, m + N);

  long double lo = 0, hi = K * H, mid;
  for (i = 0; i < ITER; ++i) {
    mid = (lo + hi) / 2;
    if (check(mid))
      hi = mid;
    else
      lo = mid;
  }
  check(hi);

  vector<int> m2(m, m + N);
  for (i = 0; i < N; ++i)
    if (m1[i] != m2[i])
      cerr << i << ' ' << m1[i] << ' ' << m2[i] << '\n';
  assert(equal(m1.begin(), m1.end(), m2.begin()));

  for (i = 0; i < K; ++i) {
    cout << sol[i] + 1;
    if (i == K - 1)
      cout << '\n';
    else
      cout << ' ';
  }

  cout << flush;
  return 0;
}