#include <bits/stdc++.h> #include "books.h" #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> typedef long long ll; using namespace std; using namespace __gnu_pbds; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; void solve(int N, int K, ll A, int S) { int lo = 1, hi = N; // binary search: pierwsze skim(i) >= A 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: 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 CIĄGŁYCH 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]; } if (A <= suma && suma <= 2 * A) { vector<int> ans; for (int i = (int)val.size() - K; i < (int)val.size(); ++i) ans.push_back(ind[i]); answer(ans); return; } impossible(); }