Pasted

#include <vector>
#include "optimization.h"
#include <cmath>
#include <algorithm>
#include <functional>
using namespace std;
typedef pair<int, int> pii;
 
vector<pii> a;
vector<pair<double, int>> ans;
vector<double> scaledVector;
 
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 = 1e6;
 
    for (int kk = 0; kk < 50; ++kk) {
        double m = (l + r) / 2;
        for (int i = 0; i < n; ++i) {
            pii x = a[i];
            scaledVector[i] = x.first - m * x.second;
        }
        nth_element(scaledVector.begin(), scaledVector.begin() + k, scaledVector.end());
        double sum = 0;
        for (int i = k; 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);
    }
    sort(ans.rbegin(), ans.rend());
    for (int i = 0; i < k; ++i) {
         writeInt(ans[i].second + 1, ' ');
    }
    writeChar('\n');
    return 0;
}