#include <bits/stdc++.h>
#include "books.h"
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.
//
vector<long long> books;
vector<int> ans;
long long get_books(int a) {
if (books[a]) return books[a];
return books[a] = skim(a);
}
void solve(int n, int k, long long a, int s) { // check kamia mlkia pou vazeis polles fores to idio
// TODO implement this function
books.resize(n+1);
long long sm = 0;
for (int i = 1; i <= k; i++) sm += get_books(i);
if (sm > 2*a) impossible();
if (sm >= a) {
for (int i = 1; i <= k; i++) ans.push_back(i);
answer(ans);
}
sm = 0;
int l = 1, r = n, fp = n+1;
while (l <= r) {
int m = (l + r) / 2;
if (get_books(m) < a) {
l = m+1;
}
else {
fp = m;
r = m-1;
}
}
if (fp != n+1) {
if (fp <= k) impossible();
sm = get_books(fp);
for (int i = 1; i < k; i++) {
sm += get_books(i);
}
if (sm <= 2*a) {
for (int i = 1; i < k; i++) ans.push_back(i);
ans.push_back(fp);
answer(ans);
}
sm = 0;
}
// we have fp > k
for (int i = fp - k; i < fp; i++) sm += get_books(i);
if (sm < a) impossible();
for (int i = fp-k; i < fp; i++) ans.push_back(i);
int ind = 1;
while (sm > 2*a) {
ans[ind] = ind;
sm += get_books(ind) - get_books(ind - 1 + fp - k);
ind++;
}
answer(ans);
}
