#include <bits/stdc++.h>
#include "books.h"
#ifndef EVAL
#include "grader.cpp"
#endif
using namespace std;
using ll = long long;
void solve(int n, int k, ll a, int s) {
vector<ll> is(n + 1, -1);
int c = 0;
auto ask = [&](int i){
if(~is[i]) return is[i];
assert(c < s);
is[i] = skim(i), c++;
return is[i];
};
int l = 1, r = n;
while(l < r){
int m = (l + r) >> 1;
if(a < ask(m)) r = m;
else l = m + 1;
}
int p = l;
if(ask(p) >= a * 2) p--;
if(p < k){
impossible();
return;
}
vector<ll> pos, val;
for(int i=1;i<=k;i++){
pos.push_back(i);
val.push_back(ask(i));
}
for(int i=max(k, p-k) + 1;i<=p;i++){
pos.push_back(i);
val.push_back(ask(i));
}
int m = pos.size(), res = -1;
for(int mask=0;mask < (1 << m);mask++){
if(__builtin_popcount(mask) != k) continue;
ll sum = 0;
for(int i=0;i<m;i++){
if(mask >> i & 1) sum += val[i];
}
if(a <= sum && sum <= a * 2){
res = mask;
}
}
if(res == -1) { impossible(); return; }
vector<int> rr;
for(int i=0;i<m;i++){
if(res >> i & 1) rr.push_back(pos[i]);
}
//~ for(auto x : rr) cout<<is[x]<<" ";
//~ cout<<"\n";
answer(rr);
//~ vector<ll> L, R;
//~ for(int i=1;i<=k;i++){
//~ L.push_back(ask(i));
//~ }
//~ for(int i=p-k+1;i<=p;i++){
//~ R.push_back(ask(i));
//~ }
//~ if(accumulate(R.begin(), R.end(), 0ll) < a
//~ || accumulate(L.begin(), L.end(), 0ll) > a * 2) { impossible(); return; }
//~ int fix=-1;
//~ for(int i=1;i<=k;i++){
//~ ll sum = 0;
//~ for(int j=0;j<i;j++) sum += L[j];
//~ for(int j=k-1;j>=i;j--) sum += R[j];
//~ if(sum > a * 2) continue;
//~ fix = i; break;
//~ }
//~ ll sum = 0;
//~ for(int j=0;j<fix-1;j++) sum += L[j];
//~ for(int j=k-1;j>=fix;j--) sum += R[j];
//~ l = fix, r = p - k + fix;
//~ while(l < r){
//~ int m = (l + r) >> 1;
//~ if(ask(m) + sum < a) l = m + 1;
//~ else r = m;
//~ }
//~ sum += ask(l);
//~ if(a <= sum && sum <= a * 2){
//~ vector<int> res;
//~ for(int i=1;i<fix;i++) res.push_back(i);
//~ res.push_back(l);
//~ for(int i=p-k+fix+1;i<=p;i++) res.push_back(i);
//~ answer(res);
//~ } else impossible();
}
/*
15 3 42 12
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
*/
Compilation message
watchmen.cpp:3:10: fatal error: books.h: No such file or directory
3 | #include "books.h"
| ^~~~~~~~~
compilation terminated.
