#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.
//
typedef long long ll;
typedef vector<ll> vi;
#define sz(x) (int)(x).size()
ll A;
int N, K, S;
vi store;
ll mySkim(int x)
{
assert(1 <= x && x <= N);
if (store[x] == -1)
store[x] = skim(x);
return store[x];
}
ll eval(vi &ans)
{
assert(sz(ans) == K);
ll checkSum = 0;
for (ll x : ans)
checkSum += mySkim((int)x);
return checkSum;
}
void myImpossible() { impossible(); }
void myAnswer(vi &ans)
{
assert(sz(ans) == K);
ll checkSum = eval(ans);
assert(A <= checkSum && checkSum <= 2 * A);
vector<int> yourAns;
for (ll x : ans)
yourAns.push_back((int)x);
answer(yourAns);
}
void solve(int _N, int _K, long long _A, int _S)
{
A = _A, N = _N, K = _K, S = _S;
store.assign(N + 1, -1); // starting with 1 index
if (S == N) // Sub 1 & 2
{
for (int i = 1; i <= N; ++i)
mySkim(i);
ll psum = 0;
for (int i = 1; i <= K; ++i)
psum += mySkim(i);
if (psum > 2 * A)
myImpossible();
int idx = 1;
while (idx + K <= N && psum < A)
{
psum -= mySkim(idx);
psum += mySkim(idx + K);
++idx;
}
if (psum > 2 * A)
{
assert(mySkim(idx + K - 1) > A);
vi ans;
for (int i = 1; i <= K - 1; ++i)
ans.push_back(i);
ans.push_back(idx + K - 1);
if (eval(ans) <= 2 * A)
myAnswer(ans);
else
myImpossible();
}
else if (psum >= A)
{
vi ans;
for (int i = idx; i < idx + K; ++i)
ans.push_back(i);
myAnswer(ans);
}
else
myImpossible();
}
else
{ // Sub 4
ll psum = 0;
for (int i = 1; i <= K - 1; ++i)
psum += mySkim(i);
if (psum + mySkim(K) > 2 * A)
{
myImpossible();
return;
}
// binary search for frist Element below 2 * A - psum
int l = K, r = N, m;
while (l < r)
{
m = (l + r + 1) / 2;
if (mySkim(m) + psum > 2 * A - psum)
r = m - 1;
else
l = m;
}
psum += mySkim(l);
if (A <= psum && psum <= 2 * A)
{
vi ans;
for (int i = 1; i <= K - 1; ++i)
ans.push_back(i);
ans.push_back(l);
myAnswer(ans);
return;
}
else
{
for (int vorne = 0; vorne <= K; ++vorne)
{
vi ans;
for (int i = 1; i <= vorne; ++i)
ans.push_back(i);
for (int i = l; i > l - K + vorne; --i)
ans.push_back(i);
ll check = eval(ans);
if (A <= check && check <= 2 * A)
{
myAnswer(ans);
return;
}
}
myImpossible();
}
}
}
