#include <bits/stdc++.h>
#include "books.h"
#define ll long long
using namespace std;
//
// --- Sample implementation for the task books ---
//
// To compile this program with the sample grader, place:
// books.h books_sample.cpp sample_grader.cpp
// in a single folder and run:
// g++ books_sample.cpp sample_grader.cpp
// in this folder.
//
ll doquery(int i, map<int,ll>& storeRes){
//cout << "doing query " << i << endl;
if(storeRes.find(i) != storeRes.end()){
//cout << "stored val " << i << endl;
return storeRes[i];
}
else{
return storeRes[i] = skim(i);
}
}
void solve(int N, int K, long long A, int S) {
map<int,ll> storeRes;
//find the first element such that Kfirst + x >= A
ll firstKm1 = 0;
for(int i = 1; i <= K-1; i++){
firstKm1 += doquery(i,storeRes);
}
//cout << firstKm1 << endl;
int l = K-1;
int r = N+1;
while(l+1 < r){
int mid = (l+r)/2;
ll res = doquery(mid,storeRes);
if(res + firstKm1 < A) l = mid;
else r = mid;
}
if(r != N+1){
if(doquery(r,storeRes) + firstKm1 <= 2*A){
vector<int> ans(K);
ans[K-1] = r;
for(int i = 1; i< K; i++){
ans[i-1] = i;
}
answer(ans);
return;
}
}
//ta från bakom tills det blir mer än A
int first = l;
ll pref = 0;
if(l < K){
impossible();
return;
}
for(int i = 1; i <= K; i++){
pref += doquery(first - i + 1,storeRes);
if(pref >= A){
vector<int> ans;
for(int j = 1; j<= K- i; j++){
ans.push_back(j);
}
for(int j = first-i +1; j <= first; j++){
ans.push_back(j);
}
answer(ans);
return;
}
}
impossible();
}
