| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1111929 | fryingduc | 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;
#ifdef duc_debug
#include "bits/debug.h"
#else
#include "books.h"
#define debug(...)
#endif
const int maxn = 1e5 + 5;
int n, k, q;
long long m;
long long a[maxn];
long long ans[maxn];
int cnt_asks;
long long ask(int id) {
if(a[id]) return a[id];
++cnt_asks;
if(cnt_asks > q) {
assert(0);
exit(0);
}
#ifdef duc_debug
return a[id] = ans[id];
#else
a[id] = skim(id);
return a[id] = x;
#endif
}
void solve(int N, int K, long long A, int S) {
n = N, k = K, m = A, q = S;
long long sum = 0;
for(int i = 1; i <= k; ++i) {
sum += ask(i);
}
if(sum > 2 * m) {
impossible();
return;
}
sum -= a[k];
int l = k, r = n;
int res = -1;
while(l <= r) {
int mid = (l + r) >> 1;
if(sum + ask(mid) >= m) {
res = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
if(res != -1) {
if(a[res] + sum <= 2 * m) {
vector<int> ds;
for(int i = 1; i < k; ++i) ds.push_back(i);
ds.push_back(res);
answer(ds);
return;
}
} else {
res = n + 1;
}
sum += a[--res];
set<int> s;
for(int i = 1; i < k; ++i) s.insert(i);
s.insert(res);
for(int i = res - 1, j = k - 1; i > 0 and j > 0; --i, --j) {
if(sum >= m) break;
sum -= ask(j);
s.erase(j);
s.insert(i);
sum += ask(i);
}
if(sum < m || sum > m * 2) {
impossible();
return;
}
vector<int> ds;
for(auto i:s) ds.push_back(i);
answer(ds);
}