| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 946071 | Pikachu | 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(long long n, long long k, long long A, long long s)
{
vector<long long> a(n + 2, -1);
long long sum = 0;
for (long long i = 1; i <= k; i++) {
a[i] = skim(i);
sum += a[i];
}
if (sum > 2ll * A) impossible();
if (sum >= A) {
vector<int> ans;
for (long long i = 1; i <= k; i++) ans.push_back(i);
answer(ans);
}
long long l = 1, r = n, oe = n + 1;
while (l <= r) {
long long mid = (l + r) >> 1;
if (skim(mid) >= A) {
oe = mid;
r = mid - 1;
}
else l = mid + 1;
}
if (oe != n + 1) {
if (sum - a[k] + a[oe] <= 2ll * A) {
vector<int> ans;
for (long long i = 1; i < k; i++) {
ans.push_back(i);
}
ans.push_back(oe);
answer(ans);
}
}
oe--;
long long dak = 0;
for (long long i = oe; i > oe - k; i--) {
a[i] = skim(i);
dak += a[i];
}
if (dak < A) impossible();
for (long long i = oe; i > oe - k; i--) {
vector<int> ans;
long long lef = k - (oe - i + 1);
long long sum = 0;
for (long long j = 1; j <= lef; j++) {
ans.push_back(j);
sum += a[j];
}
for (long long j = i; j <= oe; j++) {
ans.push_back(j);
sum += a[j];
}
if (A <= sum && sum <= 2ll * A) {
answer(ans);
}
}
impossible();
}