Advertisement
Guest User

Untitled

a guest
Mar 25th, 2012
303
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.04 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <algorithm>
  5. #define MAXN 100005
  6. using namespace std;
  7.  
  8. typedef long long int ll;
  9. typedef long double Lf;
  10. int N,K,A[MAXN],tmp;
  11. Lf H,M[MAXN],V[MAXN];
  12. Lf lo,hi,mid;
  13. vector <ll> S;
  14.  
  15. bool cmp(int a,int b){
  16. if(M[a] != M[b]) return M[a] < M[b];
  17. return V[a] < V[b];
  18. }
  19.  
  20. bool can(Lf VAL){
  21. S.clear();
  22. for(int i=1;i<=N;++i){
  23. S.push_back((ll)(VAL * V[A[i]] / H));
  24. }
  25. tmp = 0;
  26. for(int i=0;i<(int)S.size();++i)
  27. if(S[i] > tmp) ++tmp;
  28. return tmp >= K;
  29. }
  30.  
  31. int main(){
  32. cin >> N >> K >> H;
  33. for(int i=1;i<=N;++i) cin >> M[i];
  34. for(int i=1;i<=N;++i) cin >> V[i];
  35. for(int i=1;i<=N;++i) A[i] = i;
  36. sort(A+1,A+N+1,cmp);
  37. lo = 1, hi = (Lf)H * (Lf)(K);
  38. for(int it=0;it<90;++it){
  39. mid = (hi+lo)/2.0;
  40. if(can(mid)) hi = mid;
  41. else lo = mid;
  42. }
  43. S.clear();
  44. for(int i=1;i<=N;++i) S.push_back((ll)(hi * V[A[i]] / H));
  45. tmp = 0;
  46. for(int i=0;i<(int)S.size();++i)
  47. if(S[i] > tmp){
  48. cout << A[i+1] << " ";
  49. ++tmp;
  50. if(tmp >= K) break;
  51. }
  52. cout << endl;
  53. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement