Advertisement
Guest User

Untitled

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