Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <algorithm>
- #define MAXN 100005
- #define EPSILON 1e-12
- using namespace std;
- typedef long long int ll;
- typedef long double Lf;
- int N,K,A[MAXN],tmp;
- Lf H,M[MAXN],V[MAXN];
- Lf lo,hi,mid;
- vector <ll> S;
- bool eq(Lf a,Lf b){
- return a-b < EPSILON && b-a < EPSILON;
- }
- bool cmp(int a,int b){
- if(M[a] != M[b]) return M[a] < M[b];
- return V[a] < V[b];
- }
- bool can(Lf VAL){
- S.clear();
- for(int i=1;i<=N;++i){
- S.push_back((ll)(VAL * V[A[i]] / H));
- }
- tmp = 0;
- for(int i=0;i<(int)S.size();++i)
- if(S[i] > tmp) ++tmp;
- return tmp >= K;
- }
- int main(){
- cin >> N >> K >> H;
- for(int i=1;i<=N;++i) cin >> M[i];
- for(int i=1;i<=N;++i) cin >> V[i];
- for(int i=1;i<=N;++i) A[i] = i;
- sort(A+1,A+N+1,cmp);
- lo = 1, hi = (Lf)H * (Lf)(K);
- while(!eq(hi,lo)){
- mid = (hi+lo)/2.0;
- if(can(mid)) hi = mid;
- else lo = mid;
- }
- S.clear();
- for(int i=1;i<=N;++i) S.push_back((ll)(hi * V[A[i]] / H));
- tmp = 0;
- for(int i=0;i<(int)S.size();++i)
- if(S[i] > tmp){
- cout << A[i+1] << " ";
- ++tmp;
- if(tmp >= K) break;
- }
- cout << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement