#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); } } ll suma = 0; set<int> free, taken; for(int i=K+1; i<lo; ++i) free.insert(i); queue<int> Q; for(int i=1; i<=K; ++i) { suma += a[i]; Q.push(i); taken.insert(i); } if(suma >= A && suma <= 2*A) { vector<int> ans; for(auto x : taken) ans.push_back(x); answer(ans); } for(int i=1; i<=K; ++i) { int v = Q.front(); Q.pop(); suma -= a[v]; free.insert(v); int u = *free.rbegin(); suma += a[u]; free.erase(u); taken.erase(v); taken.insert(u); if(suma >= A && suma <= 2*A) { vector<int> ans; for(auto x : taken) ans.push_back(x); answer(ans); } } impossible(); }