#include "books.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// ll skim(int i)
// {
// return 0LL;
// }
// void answer(vector<int> v) {}
// void impossible() {}
int bin_search(int n, ll a)
{
int l = 1, r = n;
while (l < r)
{
int mid = (l+r+1)>>1;
if (skim(mid) <= a)
l = mid;
else
r = mid-1;
}
return l;
}
bool try_books(vector<pair<ll, int>> books, ll a)
{
ll s = 0LL;
for (auto[val, idx] : books)
s += val;
if (a <= s && s <= 2LL*a)
{
vector<int> ans(books.size());
for (int i = 0; i < books.size(); i++)
ans[i] = books[i].second;
answer(ans);
return true;
}
return false;
}
void solve(int n, int k, ll a, int s)
{
if (skim(1) > a)
{
impossible();
return;
}
vector<pair<ll, int>> skimmed;
int q = bin_search(n, a);
if (q < k-1)
{
impossible();
return;
}
else if (q < 2*k)
{
for (int i = 1; i <= q; i++)
skimmed.push_back({skim(i), i});
}
else
{
for (int i = 1; i <= k; i++)
skimmed.push_back({skim(i), i});
for (int i = q-k+1; i <= q; i++)
skimmed.push_back({skim(i), i});
}
if (q+1 <= n)
{
vector<pair<ll, int>> books;
for (int i = 0; i < k-1; i++)
books.push_back(skimmed[i]);
books.push_back({skim(q+1), q+1});
if (try_books(books, a))
return;
}
for (int i = 0; i+k-1 <= skimmed.size(); i++)
{
vector<pair<ll, int>> books;
for (int j = i; j < i+k; j++)
books.push_back(skimmed[j]);
if (try_books(books, a))
return;
}
impossible();
}
