#include <bits/stdc++.h>
#include "books.h"
using namespace std;
//
// --- Sample implementation for the task books ---
//
// To compile this program with the sample grader, place:
// books.h books_sample.cpp sample_grader.cpp
// in a single folder and run:
// g++ books_sample.cpp sample_grader.cpp
// in this folder.
//
void subtask2(int N, int K, long long A, int S) {
vector<long long> a(N);
for (int i=0;i<N;i++) {
a[i] = skim(i+1);
}
long long pref = 0;
for (int i=0;i<K;i++) {
pref += a[i];
}
if (pref > 2*A) {
impossible();
return;
}
auto it = lower_bound(a.begin(), a.end(), A);
if (it != a.end()) {
long long num = *it;
for (int i=0;i<K-1;i++) num += a[i];
if (num <= 2LL*A) {
vector<int> idx;
for (int i=0;i<K-1;i++) idx.push_back(i+1);
idx.push_back(distance(a.begin(), it)+1);
answer(idx);
return;
}
}
while (a.back() >= A)a.pop_back();
for (int i=0;i<(int)a.size()-K+1;i++) {
long long sum = 0;
for (int j=0;j<K;j++) {
sum += a[j+i];
}
if (A <= sum && sum <= 2LL*A) {
vector<int> idx;
for (int j=0;j<K;j++) {
idx.push_back(i+j+1);
}
answer(idx);
return;
}
}
impossible();
}
vector<int> vals;
int toge;
int qu;
int query(int i) {
if (vals[i] == -1) {
qu++;
if (qu > toge) {
assert(false);
}
vals[i] = skim(i+1);
}
return vals[i];
}
void solve(int N, int K, long long A, int S) {
toge = S;
if (N <= S) {
subtask2(N,K,A,S);
}
vals.assign(N, -1);
// check first K values
long long sum = 0;
for (int i=0;i<K;i++) {
sum += query(i);
}
if (sum > 2*A) {
impossible();
return;
}
if (sum >= A) {
vector<int> idx;
for (int i=0;i<K;i++) {
idx.push_back(i+1);
}
answer(idx);
return;
}
// binary search for the first value greater or equal to A
int l = K, r = N-1;
int ans = -1;
long long valans = -1;
while (l <= r) {
int m = l + (r-l)/2;
long long val = query(m);
if (val == A) {
ans = m;
valans = A;
break;
}
if (val < A) {
l = m+1;
}
else {
ans = m;
valans = val;
r = m-1;
}
}
// check if prefix + a is fitting
int last = N-1;
if (ans != -1) {
long long cand = sum - query(K-1) + valans;
long long cand2 = sum - query(0) + valans;
if (A <= cand && cand <= 2*A) {
vector<int> idx;
for (int i=0;i<K-1;i++)idx.push_back(i+1);
idx.push_back(ans+1);
answer(idx);
return;
}
if (A <= cand2 && cand2 <= 2*A) {
vector<int> idx;
for (int i=1;i<K;i++)idx.push_back(i+1);
idx.push_back(ans+1);
answer(idx);
return;
}
last = ans-1;
}
long long suf = 0;
for (int i=0;i<K;i++) {
suf += query(last - i);
}
if (A <= suf && suf <= 2*A) {
vector<int> idx;
for (int i=0;i<K;i++) {
idx.push_back(last - i + 1);
}
answer(idx);
return;
}
if (suf < A) {
impossible();
return;
}
// now prefix has sum < a, and suffix has sum > 2*a
// then, there must be a subarray, such that the sum is exactly in between
// why? because if that wasn't true, then the added contribution must be greater than a
// however, since all elements are smaller than a, any difference between two elements cannot be greater
// that a, hence, there must be a subarray with the desired sum
l = 0, r = last - K + 1;
while (l <= r) {
int m = l + (r-l)/2;
long long tmpSum = 0;
for (int i=0;i<K;i++) {
tmpSum += query(i+m);
}
if (A <= tmpSum && tmpSum <= 2*A) {
vector<int> idx;
for (int i=0;i<K;i++)idx.push_back(i+m+1);
answer(idx);
return;
}
else if (tmpSum < A) {
l = m+1;
}
else {
r = m-1;
}
}
assert(false);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
7 ms |
344 KB |
Output is correct |
| 3 |
Correct |
4 ms |
344 KB |
Output is correct |
| 4 |
Correct |
5 ms |
344 KB |
Output is correct |
| 5 |
Correct |
4 ms |
340 KB |
Output is correct |
| 6 |
Correct |
5 ms |
344 KB |
Output is correct |
| 7 |
Correct |
4 ms |
344 KB |
Output is correct |
| 8 |
Correct |
4 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
5 ms |
344 KB |
Output is correct |
| 3 |
Correct |
5 ms |
344 KB |
Output is correct |
| 4 |
Correct |
4 ms |
344 KB |
Output is correct |
| 5 |
Correct |
5 ms |
344 KB |
Output is correct |
| 6 |
Correct |
4 ms |
344 KB |
Output is correct |
| 7 |
Correct |
5 ms |
344 KB |
Output is correct |
| 8 |
Correct |
5 ms |
344 KB |
Output is correct |
| 9 |
Correct |
143 ms |
600 KB |
Output is correct |
| 10 |
Correct |
120 ms |
600 KB |
Output is correct |
| 11 |
Correct |
123 ms |
600 KB |
Output is correct |
| 12 |
Correct |
110 ms |
600 KB |
Output is correct |
| 13 |
Correct |
116 ms |
600 KB |
Output is correct |
| 14 |
Correct |
131 ms |
852 KB |
Output is correct |
| 15 |
Correct |
116 ms |
600 KB |
Output is correct |
| 16 |
Correct |
121 ms |
600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
