| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1304621 | vlomaczk | A Difficult(y) Choice (BOI21_books) | C++20 | 0 ms | 0 KiB |
#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(ll N, ll K, ll A, ll S) {
ll lo=1, hi=N;
while(lo < hi) {
ll mid = (lo+hi)/2;
if(skim(mid) < A) lo = mid + 1;
else hi = mid;
}
if(lo < K) {
impossible();
return;
}
if(lo < K) impossible();
vector<ll> val, idx;
for(ll i=1; i<=K; ++i) {
val.push_back(skim(i));
idx.push_back(i);
}
for(ll i=max(K, lo-K)+1; i<=lo; ++i) {
val.push_back(skim(i));
idx.push_back(i);
}
ll suma = skim(lo);
for(ll i=0; i<K-1; ++i) suma += val[i];
if(A<=suma && suma<=2*A) {
vector<ll> ans = {lo};
for(ll i=1; i<K; ++i) ans.push_back(i);
answer(ans);
}
suma = 0;
for(ll i=0; i<K; ++i) suma += val[i];
if(A<=suma && suma<=2*A) {
vector<ll> ans;
for(ll j=0; j<K; ++j) ans.push_back(idx[j]);
answer(ans);
}
for(ll i=K; i<val.size(); ++i) {
suma -= val[i-K];
suma += val[i];
if(A<=suma && suma<=2*A) {
vector<ll> ans;
for(ll j=i-K; j<i; ++j) ans.push_back(idx[j]);
answer(ans);
}
}
impossible();
}