Pasted

#include <vector>
#include "optimization.h"
#include <cmath>
using namespace std;
typedef pair<int, int> pii;
 
vector<pii> a;
vector<pair<double, int>> ans;
vector<double> scaledVector;
int partition(int l, int r, int pI) {
    int pivot = scaledVector[pI];
    swap(scaledVector[pI], scaledVector[r]);
    int store = l;
    for (int i = l; i < r; ++i) {
        if(scaledVector[i] < pivot) {
            swap(scaledVector[i], scaledVector[store++]);
        }
    }
    swap(scaledVector[r], scaledVector[store]);
    return store;
}
 
int partition_ans(int l, int r, int pI) {
    int pivot = ans[pI].first;
    swap(ans[pI], ans[r]);
    int store = l;
    for (int i = l; i < r; ++i) {
        if(ans[i].first < pivot) {
            swap(ans[i], ans[store++]);
        }
    }
    swap(ans[r], ans[store]);
    return store;
}
 
int select(int l, int r, int k, int (*part)(int, int, int)) {
    if(l == r) return l;
//    int pI = (l+r)/2;
    int pI = l + ((int) floor(rand() % (r - l)));
    pI = part(l, r, pI);
    if(pI == k) {
        return pI;
    } else if(pI < k) {
        return select(pI + 1, r, k - pI, part);
    } else {
        return select(l, pI - 1, k, part);
    }
}
 
int main() {
    int n = readInt(), k = readInt();
    a.resize(n);
    scaledVector.resize(n);
    for (int i = 0; i < n; ++i) {
        a[i] = make_pair(readInt(), readInt());
    }
    double l = 0, r = 1e7;
 
    for (int kk = 0; kk < 100000; ++kk) {
        double m = (l + r) / 2;
        for (int i = 0; i < n; ++i) {
            pii x = a[i];
            scaledVector[i] = x.first - m * x.second;
        }
        int pI = select(0, n-1, k-1, &partition);
        double sum = 0;
        for (int i = pI; i < n; ++i) {
            sum += scaledVector[i];
        }
        if(sum >= 0) {
            l = m;
        } else {
            r = m;
        }
    }
    ans.resize(n);
    for (int i = 0; i < n; ++i) {
        pii x = a[i];
        ans[i] = make_pair(x.first - l * x.second, i);
    }
//    int ansPi = select(0, n, k-1, &partition_ans);
    sort(ans.begin(), ans.end());
    for (int i = 0; i < k; ++i) {
         writeInt(ans[n-i-1].second + 1, ' ');
    }
    writeChar('\n');
    return 0;
}