#include "bits/stdc++.h" #include "books.h" using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); // https://codeforces.com/blog/entry/79148 class Timer: chrono::high_resolution_clock { const time_point start_time; public: Timer(): start_time(now()) {} rep elapsed_time() const { return chrono::duration_cast<chrono::milliseconds>(now() - start_time).count(); } } timer; void solve(int n, int k_, ll a_, int s) { ull k = k_, a = a_; int l = 1, r = n; vector<ull> res(n + 1, 0); while (r - l >= 2) { int m = (l + r) / 2; res[m] = skim(m) * k; if (res[m] >= a) { r = m; } else { l = m; } } if (!res[l]) { res[l] = skim(l) * k; } if (!res[l + 1]) { res[l + 1] = skim(l + 1) * k; } if (!res[r]) { res[r] = skim(r) * k; } ull p; if (res[l] >= a) { p = l; } else if (res[l + 1] >= a) { p = l + 1; } else { p = r; } p = max(p, k); ull cur = res[p]; for (int i = p - 1; i >= p - k + 1; i--) { if (!res[i]) { res[i] = skim(i) * k; } cur += res[i]; } vector<int> ans; while (true) { if (cur >= k * a && cur <= 2 * k * a) { for (int i = p - k + 1; i <= p; i++) { ans.push_back(i); } answer(ans); break; } if (cur > 2 * k * a) { cur = res[p]; for (int i = 1; i < k; i++) { if (!res[i]) { res[i] = skim(i) * k; } cur += res[i]; } if (cur >= k * a && cur <= 2 * k * a) { for (int i = 1; i < k; i++) { ans.push_back(i); } ans.push_back(p); answer(ans); } else { impossible(); } break; } cur -= res[p - k + 1]; p++; if (p > n) { impossible(); break; } if (!res[p]) { res[p] = skim(p) * k; } cur += res[p]; } }