#include <bits/stdc++.h>
#include "books.h"
using namespace std;
//#define int long long
//#include <iostream>
//#include <algorithm>
#define coffeebeans 100000000000 //10e11
long long currsum;
bool checkers(int x, int K, vector<pair<int,long long>> &ans, long long A)
//return false if adding would make it too large
//return true if not and insert x into the vector
//ans : {index, value} pair
{
long long temp1 = skim(x);
long long cantake = (2 * A) - currsum;
if ((currsum + (temp1 - ans[K].second)) > (2 * A) || (temp1 > (2 * A)))
{
return false;
}
else
{
long long hi = K, lo = 1, mid;
while (hi > lo)
{
//printf("stuck in checkers\n");
mid = (hi + lo)/2;
if (((temp1 - ans[mid].second) <= cantake)) //won't exceed : go lower
{
//printf("replacing %d is ok\n",mid);
hi = mid;
}
else
{
lo = mid + 1;
}
}
currsum += (temp1 - ans[lo].second);
//cout << "x : " << x << "\n";
ans[lo] = {x,temp1};
//printf("replaced %d", lo);
}
//printf ("this is currsum now : %d",currsum);
sort(ans.begin() + 1, ans.end());
return true;
}
void solve(int N, int K, long long A, int S)
{
vector<pair<int,long long>>ans(K + 1);
long long temp1,temp2;
//edge cases:
long long catson = 0;
if (A >= coffeebeans)
{
//printf("you entered the loop\n");
vector<int>koko;
for (int a = (N - K + 1); a <= N; a++)
{
koko.push_back(a);
}
for (int a = N; a > (N - K); a--)
{
temp1 = skim(a);
if (temp1 >= A)
{
answer(koko);
}
else
{
catson += temp1;
}
}
if (catson >= A)
{
answer(koko);
}
else
{
impossible();
}
}
//end of edge cases
for (int a = 1; a <= K; a++)
{
temp2 = skim(a);
ans[a] = {a,temp2};
currsum += temp2;
}
if (currsum > (2 * A))
{
impossible();
}
vector<int>kokonut;
if ((currsum >= A) && (currsum <= (2 * A)))
{
for (int a = 1; a <= K; a++)
{
kokonut.push_back(ans[a].first);
}
answer(kokonut);
}
int hi = N,lo = K + 1,mid;
//int anss;
while (hi >= lo)
{
//printf("stuck in solve\n");
mid = lo + (hi + lo)/2;
if (checkers(mid, K, ans, A)) //keyi
{
//anss = mid;
lo = mid + 1;
}
else
{
hi = mid - 1;
}
//printf("\n%d is between %d and %d", currsum, A, (2 * A));
if ((currsum >= A) && (currsum <= (2 * A)))
{
for (int a = 1; a <= K; a++)
{
kokonut.push_back(ans[a].first);
}
answer(kokonut);
}
}
//printf("is this one\n");
impossible();
}
