#include "books.h"
#include <vector>
#include <iostream>
using namespace std;
using ll = long long;
//
// --- 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.
//
void solve(int N, int K, long long A, int S) {
int lo = 1, hi = N+1;
// find the first book larger than A
while (hi-lo > 1) {
int mid = (lo+hi)/2;
ll x = skim(mid);
if (x > A)
hi = mid;
else
lo = mid;
}
if (hi < K)
impossible();
int idx = hi;
vector<int> a(K+1);
vector<ll> books(K+1);
ll sum = 0;
for (int i = 1; i <= K; i++) {
a[i] = i;
books[i] = skim(i);
sum += books[i];
}
if (sum > 2*A) {
impossible();
return;
}
if (idx <= N) {
ll temp = skim(idx);
if (temp+sum-books[K] >= A && temp+sum-books[K] <= 2*A) {
books[K] = idx;
vector<int> ans;
a[K] = idx;
for (int i = 1; i <= K; i++)
ans.push_back(a[i]);
answer(ans);
}
}
ll sum2 = 0;
vector<ll> b;
for (int i = idx-K; i < idx; i++) {
b.push_back(skim(i));
sum2 += b.back();
}
if (sum2 < A)
impossible();
if (sum >= A && sum <= 2*A) {
vector<int> ans;
for (int i = 1; i <= K; i++)
ans.push_back(a[i]);
answer(ans);
return;
}
for (int i = K; i >= 1; i--) {
// move the ith book to the end
sum -= books[i];
ll x = b[K-i];
sum += x;
a[i] = idx-K+i-1;
if (sum >= A && sum <= 2*A)
break;
}
vector<int> ans;
for (int i = 1; i <= K; i++) {
ans.push_back(a[i]);
}
answer(ans);
}
