#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 solve(int N, int K, long long A, int S) {
// TODO implement this function
/*
if (skim(2) == 42) {
impossible();
} else {
answer({1, 3});
}*/
//head must be <= floor(A/K)
vector<long long> dis(N+1, -1);
int lo = 1;
int hi = N;
int mid;
long long tgt = A/K;
int bst = N;
//cout << tgt << '\n';
while (lo <= hi){
mid = (lo+hi)/2;
long long vv;
if (dis[mid] == -1){
vv = skim(mid);
dis[mid] = vv;
}
else{
vv = dis[mid];
}
if (vv >= tgt){
bst = min(bst,mid);
hi = mid-1;
}
else{
lo = mid+1;
}
}
//cout << bst << '\n';
//ok head found
for (int i = max(1,bst-K); i <= min(N,bst+K); i++){
if (dis[i] == -1){
dis[i] = skim(i);
}
}/*
vector<int> ck;
int cr = 0;
for (int i = bst; i<=min(N,bst+K-1); i++){
ck.push_back(dis[i]);
cr += dis[i];
}
if (cr >= A && cr <= 2*A){
answer(ck);
}
else{
impossible();
}*/
//now check
for (int i = 0; i<=N; i++){
//cout << dis[i] << " ";
}
//cout << '\n';
for (int i = max(1,bst-K); i<= min(N,bst+K); i++){
long long sm = 0;
vector<int> pot;
for (int j = i; j<=min(N,i+K-1); j++){
sm += dis[j];
pot.push_back(j);
}
//cout << sm << '\n';
for (auto u : pot){
//cout << u << " ";
}
//cout << '\n';
if ((sm >= A) && (sm<=2*A)){
answer(pot);
}
}
impossible();
}
Compilation message
books.cpp: In function 'void solve(int, int, long long int, int)':
books.cpp:83:13: warning: unused variable 'u' [-Wunused-variable]
83 | for (auto u : pot){
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Incorrect |
0 ms |
344 KB |
Incorrect |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Incorrect |
0 ms |
344 KB |
Incorrect |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1112 KB |
Output is correct |
2 |
Correct |
1 ms |
1112 KB |
Output is correct |
3 |
Correct |
1 ms |
1112 KB |
Output is correct |
4 |
Correct |
1 ms |
1112 KB |
Output is correct |
5 |
Correct |
1 ms |
1112 KB |
Output is correct |
6 |
Correct |
1 ms |
1112 KB |
Output is correct |
7 |
Correct |
1 ms |
1112 KB |
Output is correct |
8 |
Correct |
1 ms |
1112 KB |
Output is correct |
9 |
Correct |
1 ms |
1112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1112 KB |
Output is correct |
2 |
Correct |
1 ms |
1112 KB |
Output is correct |
3 |
Correct |
1 ms |
1112 KB |
Output is correct |
4 |
Correct |
1 ms |
1112 KB |
Output is correct |
5 |
Correct |
1 ms |
1112 KB |
Output is correct |
6 |
Correct |
1 ms |
1112 KB |
Output is correct |
7 |
Correct |
1 ms |
1112 KB |
Output is correct |
8 |
Correct |
1 ms |
1112 KB |
Output is correct |
9 |
Correct |
1 ms |
1112 KB |
Output is correct |
10 |
Correct |
1 ms |
1112 KB |
Output is correct |
11 |
Correct |
1 ms |
1112 KB |
Output is correct |
12 |
Correct |
1 ms |
1112 KB |
Output is correct |
13 |
Correct |
1 ms |
1112 KB |
Output is correct |
14 |
Correct |
1 ms |
1112 KB |
Output is correct |
15 |
Correct |
1 ms |
1112 KB |
Output is correct |
16 |
Correct |
1 ms |
1112 KB |
Output is correct |
17 |
Correct |
1 ms |
1112 KB |
Output is correct |
18 |
Correct |
1 ms |
1112 KB |
Output is correct |
19 |
Correct |
1 ms |
1112 KB |
Output is correct |
20 |
Correct |
1 ms |
1112 KB |
Output is correct |
21 |
Correct |
1 ms |
1112 KB |
Output is correct |
22 |
Correct |
1 ms |
1112 KB |
Output is correct |
23 |
Incorrect |
1 ms |
1112 KB |
Incorrect |
24 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1112 KB |
Output is correct |
2 |
Correct |
1 ms |
1112 KB |
Output is correct |
3 |
Correct |
1 ms |
1112 KB |
Output is correct |
4 |
Correct |
1 ms |
1112 KB |
Output is correct |
5 |
Correct |
1 ms |
1112 KB |
Output is correct |
6 |
Correct |
1 ms |
1112 KB |
Output is correct |
7 |
Correct |
1 ms |
1112 KB |
Output is correct |
8 |
Correct |
1 ms |
1112 KB |
Output is correct |
9 |
Correct |
1 ms |
1112 KB |
Output is correct |
10 |
Correct |
1 ms |
1112 KB |
Output is correct |
11 |
Correct |
1 ms |
1112 KB |
Output is correct |
12 |
Correct |
1 ms |
1112 KB |
Output is correct |
13 |
Correct |
1 ms |
1112 KB |
Output is correct |
14 |
Correct |
1 ms |
1112 KB |
Output is correct |
15 |
Correct |
1 ms |
1112 KB |
Output is correct |
16 |
Correct |
1 ms |
1112 KB |
Output is correct |
17 |
Correct |
1 ms |
1112 KB |
Output is correct |
18 |
Correct |
1 ms |
1112 KB |
Output is correct |
19 |
Correct |
1 ms |
1112 KB |
Output is correct |
20 |
Correct |
1 ms |
1112 KB |
Output is correct |
21 |
Correct |
1 ms |
1112 KB |
Output is correct |
22 |
Correct |
1 ms |
1112 KB |
Output is correct |
23 |
Incorrect |
1 ms |
1112 KB |
Incorrect |
24 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1112 KB |
Output is correct |
2 |
Correct |
1 ms |
1112 KB |
Output is correct |
3 |
Correct |
1 ms |
1112 KB |
Output is correct |
4 |
Correct |
1 ms |
1112 KB |
Output is correct |
5 |
Correct |
1 ms |
1112 KB |
Output is correct |
6 |
Correct |
1 ms |
1112 KB |
Output is correct |
7 |
Correct |
1 ms |
1112 KB |
Output is correct |
8 |
Correct |
1 ms |
1112 KB |
Output is correct |
9 |
Correct |
1 ms |
1112 KB |
Output is correct |
10 |
Correct |
1 ms |
1112 KB |
Output is correct |
11 |
Correct |
1 ms |
1112 KB |
Output is correct |
12 |
Correct |
1 ms |
1112 KB |
Output is correct |
13 |
Correct |
1 ms |
1112 KB |
Output is correct |
14 |
Correct |
1 ms |
1112 KB |
Output is correct |
15 |
Correct |
1 ms |
1112 KB |
Output is correct |
16 |
Correct |
1 ms |
1112 KB |
Output is correct |
17 |
Correct |
1 ms |
1112 KB |
Output is correct |
18 |
Correct |
1 ms |
1112 KB |
Output is correct |
19 |
Correct |
1 ms |
1112 KB |
Output is correct |
20 |
Correct |
1 ms |
1112 KB |
Output is correct |
21 |
Correct |
1 ms |
1112 KB |
Output is correct |
22 |
Correct |
1 ms |
1112 KB |
Output is correct |
23 |
Incorrect |
1 ms |
1112 KB |
Incorrect |
24 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1112 KB |
Output is correct |
2 |
Correct |
1 ms |
1112 KB |
Output is correct |
3 |
Correct |
1 ms |
1112 KB |
Output is correct |
4 |
Correct |
1 ms |
1112 KB |
Output is correct |
5 |
Correct |
1 ms |
1112 KB |
Output is correct |
6 |
Correct |
1 ms |
1112 KB |
Output is correct |
7 |
Correct |
1 ms |
1112 KB |
Output is correct |
8 |
Correct |
1 ms |
1112 KB |
Output is correct |
9 |
Correct |
1 ms |
1112 KB |
Output is correct |
10 |
Correct |
1 ms |
1112 KB |
Output is correct |
11 |
Correct |
1 ms |
1112 KB |
Output is correct |
12 |
Correct |
1 ms |
1112 KB |
Output is correct |
13 |
Correct |
1 ms |
1112 KB |
Output is correct |
14 |
Correct |
1 ms |
1112 KB |
Output is correct |
15 |
Correct |
1 ms |
1112 KB |
Output is correct |
16 |
Correct |
1 ms |
1112 KB |
Output is correct |
17 |
Correct |
1 ms |
1112 KB |
Output is correct |
18 |
Correct |
1 ms |
1112 KB |
Output is correct |
19 |
Correct |
1 ms |
1112 KB |
Output is correct |
20 |
Correct |
1 ms |
1112 KB |
Output is correct |
21 |
Correct |
1 ms |
1112 KB |
Output is correct |
22 |
Correct |
1 ms |
1112 KB |
Output is correct |
23 |
Incorrect |
1 ms |
1112 KB |
Incorrect |
24 |
Halted |
0 ms |
0 KB |
- |