#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;
typedef set<ll> si;
#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(si &ans)
{
assert(sz(ans) == K);
ll checkSum = 0;
for (ll x : ans)
checkSum += mySkim((int)x);
return checkSum;
}
void myImpossible() { impossible(); }
void myAnswer(si &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);
// si ans;
// for (int i = 1; i <= K - 1; ++i)
// ans.insert(i);
// ans.insert(idx + K - 1);
// if (eval(ans) <= 2 * A)
// myAnswer(ans);
// else
// myImpossible();
// }
// else if (psum >= A)
// {
// si ans;
// for (int i = idx; i < idx + K; ++i)
// ans.insert(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 first Element below 2 * A - psum
int l = K, r = N, m;
while (l < r)
{
m = (l + r + 1) / 2;
if (mySkim(m) > 2 * A - psum)
r = m - 1;
else
l = m;
}
psum += mySkim(l);
if (A <= psum && psum <= 2 * A)
{
si ans;
for (int i = 1; i <= K - 1; ++i)
ans.insert(i);
ans.insert(l);
myAnswer(ans);
return;
}
else
{
for (int vorne = 0; vorne <= K; ++vorne)
{
si ans;
for (int i = 1; i <= vorne; ++i)
ans.insert(i);
for (int i = l; i > l - K + vorne; --i)
ans.insert(i);
ll check = eval(ans);
if (A <= check && check <= 2 * A)
{
myAnswer(ans);
return;
}
}
myImpossible();
}
}
}
