| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 513864 | lorenzoferrari | 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>
using namespace std;
using LL = long long;
/*
osservazioni banali:
* se k*(k+1)/2 > a, impossibile
* altri pruning banali
what would be my strategy if I knew the whole array x?
if x[i+1] - x[i] <= a and I'm under [a,2a] and increase an index by one, I will
never be over
approach: start with [1, ..., k]
for (int i = k; i > 1; --i):
binsearch the maximum position you can place yourself
-> it works if x[i+1]-x[i] <= a
-> does it always work?
is it possible to chosoe something "too big"
*/
LL skim(int i); // 1 <= i <= N
void answer(vector<int> v);
void impossibile();
map<int, int> books;
LL ask(int i) {
if (books.find(i) == books.end())
books[i] = skim(i);
return books[i];
}
void solve(int n, int k, LL a, int s) {
vector<int> v(k);
LL sum = 0;
for (int i = 0; i < k; ++i) {
v[i] = i+1;
sum += ask(v[i]);
}
if (sum > 2 * a) impossibile();
if (a <= sum && sum <= 2 * a) answer(v);
for (int i = k - 1; i > 0; --i) {
int r = (i == k - 1 ? n+1 : v[i + 1]);
int l = i + 1;
while (r - l > 1) {
int m = (r + l) / 2;
int newsum = sum - ask(v[i]) + ask(m);
if (a <= newsum && newsum <= 2 * a) {
v[i] = m;
answer(v);
}
if (newsum < a) {
l = m;
} else {
r = m;
}
}
sum += ask(l) - ask(v[i]);
v[i] = l;
if (a <= sum && sum <= 2 * a) answer(v);
}
impossibile();
}