#include <bits/stdc++.h> #include "books.h" using namespace std; using ll = long long; void solve(int N, int K, ll A, int S) { int lo = 1, hi = N; // binary search pierwszego skim(i) >= A if (skim(N) < A) { impossible(); return; } while (lo < hi) { int mid = (lo + hi) / 2; if (skim(mid) >= A) hi = mid; else lo = mid + 1; } if (lo <= K - 1) { impossible(); return; } vector<ll> val; vector<int> ind; // 1 .. min(K, lo) for (int i = 1; i <= min(K, lo); ++i) { val.push_back(skim(i)); ind.push_back(i); } // max(K+1, lo-K+1) .. lo for (int i = max(K + 1, lo - K + 1); i <= lo; ++i) { val.push_back(skim(i)); ind.push_back(i); } // przypadek: bierzemy lo + K-1 najmniejszych ll suma = skim(lo); for (int i = 0; i < K - 1; ++i) suma += val[i]; if (A <= suma && suma <= 2 * A) { vector<int> ans; for (int i = 0; i < K - 1; ++i) ans.push_back(ind[i]); ans.push_back(lo); answer(ans); return; } // sliding window po uporządkowanych indeksach suma = 0; for (int i = 0; i < K; ++i) suma += val[i]; for (int i = K; i < (int)val.size(); ++i) { if (A <= suma && suma <= 2 * A) { vector<int> ans; for (int j = i - K; j < i; ++j) ans.push_back(ind[j]); answer(ans); return; } suma += val[i]; suma -= val[i - K]; } // ostatnie okno if (A <= suma && suma <= 2 * A) { vector<int> ans; for (int i = val.size() - K; i < (int)val.size(); ++i) ans.push_back(ind[i]); answer(ans); return; } impossible(); }