| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 403805 | wind_reaper | A Difficult(y) Choice (BOI21_books) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#ifndef LOCAL
#include "books.h"
#endif
using namespace std;
#ifdef LOCAL
int64_t X[100001];
int64_t skim(int i){
return X[i];
}
void answer(vector<int> V){
cout << "ans: \n";
for(int v : V)
cout << v << ' ';
cout << endl;
exit(0);
}
void impossible(){
cout << "impossible" << endl;
exit(0);
}
#endif
int64_t valed[100001];
int64_t val(int i){
if(valed[i]) return valed[i];
return valed[i] = skim(i);
}
void solve(int N, int K, int64_t A, int S){
vector<int> ans;
int64_t sum = 0;
for(int i = 1; i <= K; i++){
sum += val(i);
ans.push_back(i);
}
if(sum > 2*A) impossible();
if(sum >= A) answer(ans);
int l = 1, r = N, a = N;
while(l <= r){
int mid = (l + r) >> 1;
if(val(mid) <= A)
l = mid + 1;
else{
r = mid - 1;
a = mid;
}
}
int64_t T = sum - val(K) + val(a);
if(T >= A && T <= 2*A){
ans.pop_back();
ans.push_back(a);
answer(ans);
}
a--;
int j = max(a - K + 1, K + 1);
for(int i = 1; i <= K && j < a; i++, j++){
sum = sum - val(i) + val(a);
ans[i-1] = j;
if(sum >= A && sum <= 2*A)
answer(ans);
}
impossible();
}
#ifdef LOCAL
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, K, S;
int64_t A;
cin >> N >> K >> A >> S;
for(int i = 1; i <= N; i++){
cin >> X[i];
}
solve(N, K, A, S);
return 0;
}
#endif