#include <bits/stdc++.h> #include "books.h" using namespace std; typedef long long ll; void solve(int n, int k, ll s, int c) { vector < int > ans, pos; ll a[n + 1], cur = 0; for(int i = 1; i <= n; i++) a[i] = skim(i); int l = 0, r = n + 1; while(r - l > 1){ int md = (l + r) / 2; if(!a[md]) a[md] = skim(md); if(a[md] >= s) r = md; else l = md; } for(int i = 1; i <= k; i++) if(!a[i]) a[i] = skim(i); if(r <= n && r >= k){ if(!a[r]) a[r] = skim(r); cur = a[r]; for(int i = 1; i < k; i++) cur += a[i]; if(cur <= 2 * s){ for(int i = 1; i < k; i++) ans.push_back(i); ans.push_back(r), answer(ans); return; } } cur = 0; for(int i = l; i >= 1; i--){ if(!a[i]) a[i] = skim(i); if(pos.size() < k) pos.push_back(i); } if(pos.size() < k) { impossible(); return; } for(int i = 1; i < pos[k - 1] && i <= k; i++) pos.push_back(i); for(int msk = 0; msk < (1 << (int)pos.size()); msk++){ if(__builtin_popcount(msk) != k) continue; for(int i = 0; i < pos.size(); i++) if((msk >> i & 1)) cur += a[pos[i]], ans.push_back(pos[i]); if(s <= cur && cur <= 2 * s){ answer(ans); return; } cur = 0, ans.clear(); } impossible(); }