#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 __gnu_pbds; using namespace std; 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; vector<int> a(N+1); if(skim(N) >= A) { while(lo < hi) { int mid = (lo+hi)/2; if(skim(mid) < A) lo = mid + 1; else hi = mid; } a[lo] = skim(lo); } else lo = N+1; if(lo < K) impossible(); for(int i=1; i<=K; ++i) a[i] = skim(i); for(int i=lo-1; i>=lo-K; --i) a[i] = skim(i); if(lo <= N) { ll suma = a[lo]; for(int i=1; i<K; ++i) suma += a[i]; if(suma <= 2*A) { vector<int> ans = {lo}; for(int i=1; i<K; ++i) ans.push_back(i); answer(ans); } } vector<pair<int, int>> vals; for(int i=1; i<=K; ++i) vals.push_back({a[i], i}); for(int i=max(K+1, lo-K); i<lo; ++i) vals.push_back({a[i], i}); ll suma = 0; vector<int> ans; for(int i=0; i<K; ++i) { ans.push_back(vals[i].second); suma += vals[i].first; } if(A<=suma && suma<=2*A) answer(ans); for(int i=K; i<vals.size(); ++i) { suma -= vals[i-K].first; suma += vals[K].first; reverse(ans.begin(), ans.end()); ans.pop_back(); reverse(ans.begin(), ans.end()); ans.push_back(vals[i].second); if(A<=suma && suma<=2*A) answer(ans); } impossible(); }