| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 398865 | couplefire | 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>
#include "books.h"
using namespace std;
void solve(int n, int k, long long goal, int s){
// binary search for first pos >= goal
int lo = 0, hi = n-1, pos;
while(lo < hi){
int mid = lo+(hi-lo)/2;
long long val = skim(mid+1);
if(val >= goal) hi = mid;
else lo = mid+1;
}
pos = lo; long long val = skim(pos);
if(val < goal) pos = n;
vector<long long> ans;
if(pos < k-1){
impossible();
return;
}
if(pos != n){
long long sum = 0;
for(int i = 0; i<k-1; i++) sum += skim(i+1);
if(goal <= sum+val && sum+val <= 2*goal){
for(int i = 0; i<k-1; i++) ans.push_back(i+1);
ans.push_back(pos+1);
answer(ans);
return;
}
if(pos == k-1){
impossible();
return;
}
}
vector<int> arr(n);
for(int i = 0; i<k; i++) arr[i] = skim(i+1);
for(int i = pos-1; i>=pos-k; i--) arr[i] = skim(i+1);
for(int i = 0; i<=k; i++){
long long sum = 0;
for(int j = 0; j<i; j++) sum += arr[j];
for(int j = pos-1; j>=pos-(k-i); j--) sum += arr[j];
if(goal <= sum && sum <= 2*goal){
for(int j = 0; j<i; j++) ans.push_back(j+1);
for(int j = pos-1; j>=pos-(k-i); j--) ans.push_back(j+1);
answer(ans);
return;
}
}
impossible();
}