#include <bits/stdc++.h>
#include "books.h"
#define sz(x) (int)(x.size())
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.
//
map<int, long long> mp ;
long long A ;
long long ask(int x)
{
if(mp.find(x) != mp.end()) return mp[x] ;
return mp[x] = skim(x) ;
}
bool check(long long s) { return s >= A && s <= A+A ;}
void solve(int N, int K, long long a, int S)
{
A = a ;
int l = 1, r = N , mid , best = -1 ;
while( l <= r )
{
mid = (l+r)>>1 ;
if( ask(mid) <= A ) { best = mid ; l = mid+1 ; }
else r = mid-1 ;
}
if( best == -1 ) impossible() ;
vector<long long> v ;
vector<int> R ;
if( best <= 2*K )
{
for(int i = 1 ; i <= best; i++ )
{
v.push_back(ask(i)) ;
R.push_back(i) ;
}
}
else
{
for(int i = 1 ; i <= K ; i++ ) v.push_back(ask(i)) , R.push_back(i) ;
for(int i = best-K+1 ; i <= best ; i++ ) v.push_back(ask(i)) , R.push_back(i) ;
}
if(best+1 <= N && best >= K-1)
{
long long s = ask(best+1) ;
for(int i = 0 ; i < K-1 ; i++ ) s += v[i] ;
if( check(s) )
{
vector<int> ans = {best+1} ;
for(int i = 1 ; i < K ; i++ ) ans.push_back(i) ;
answer(ans) ;
return ;
}
}
if( best < K ) impossible() ;
long long s = 0 ;
for(int i = 0 ; i < K ; i++ ) s += v[i] ;
if( check(s) )
{
vector<int> ans ;
for(int i = 0 ; i < K ; i++ ) ans.push_back(R[i]) ;
answer(ans) ;
return ;
}
for(int i = K ; i < sz(v) ; i++ )
{
s -= v[i-K] ;
s += v[i] ;
if(check(s))
{
vector<int> ans ;
for(int j = i-K+1 ; j <= i ; j++ ) ans.push_back(R[j]) ;
answer(ans) ;
return ;
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
200 KB |
Output is correct |
2 |
Correct |
1 ms |
200 KB |
Output is correct |
3 |
Correct |
1 ms |
200 KB |
Output is correct |
4 |
Correct |
1 ms |
200 KB |
Output is correct |
5 |
Correct |
1 ms |
200 KB |
Output is correct |
6 |
Correct |
1 ms |
200 KB |
Output is correct |
7 |
Correct |
1 ms |
200 KB |
Output is correct |
8 |
Incorrect |
1 ms |
200 KB |
Incorrect |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
200 KB |
Output is correct |
2 |
Correct |
1 ms |
200 KB |
Output is correct |
3 |
Correct |
1 ms |
200 KB |
Output is correct |
4 |
Correct |
1 ms |
200 KB |
Output is correct |
5 |
Correct |
1 ms |
200 KB |
Output is correct |
6 |
Correct |
1 ms |
200 KB |
Output is correct |
7 |
Correct |
1 ms |
200 KB |
Output is correct |
8 |
Incorrect |
1 ms |
200 KB |
Incorrect |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
200 KB |
Output is correct |
2 |
Correct |
1 ms |
200 KB |
Output is correct |
3 |
Correct |
2 ms |
200 KB |
Output is correct |
4 |
Correct |
1 ms |
200 KB |
Output is correct |
5 |
Correct |
1 ms |
200 KB |
Output is correct |
6 |
Correct |
1 ms |
200 KB |
Output is correct |
7 |
Correct |
1 ms |
200 KB |
Output is correct |
8 |
Correct |
2 ms |
200 KB |
Output is correct |
9 |
Correct |
1 ms |
200 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
200 KB |
Output is correct |
2 |
Correct |
1 ms |
200 KB |
Output is correct |
3 |
Correct |
2 ms |
200 KB |
Output is correct |
4 |
Correct |
1 ms |
200 KB |
Output is correct |
5 |
Correct |
1 ms |
200 KB |
Output is correct |
6 |
Correct |
1 ms |
200 KB |
Output is correct |
7 |
Correct |
1 ms |
200 KB |
Output is correct |
8 |
Correct |
2 ms |
200 KB |
Output is correct |
9 |
Correct |
1 ms |
200 KB |
Output is correct |
10 |
Correct |
1 ms |
200 KB |
Output is correct |
11 |
Correct |
2 ms |
200 KB |
Output is correct |
12 |
Correct |
1 ms |
200 KB |
Output is correct |
13 |
Correct |
1 ms |
200 KB |
Output is correct |
14 |
Correct |
1 ms |
200 KB |
Output is correct |
15 |
Correct |
1 ms |
200 KB |
Output is correct |
16 |
Correct |
2 ms |
200 KB |
Output is correct |
17 |
Correct |
1 ms |
200 KB |
Output is correct |
18 |
Correct |
1 ms |
200 KB |
Output is correct |
19 |
Correct |
2 ms |
200 KB |
Output is correct |
20 |
Correct |
1 ms |
272 KB |
Output is correct |
21 |
Correct |
1 ms |
200 KB |
Output is correct |
22 |
Correct |
1 ms |
200 KB |
Output is correct |
23 |
Correct |
2 ms |
288 KB |
Output is correct |
24 |
Correct |
1 ms |
292 KB |
Output is correct |
25 |
Correct |
1 ms |
296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
200 KB |
Output is correct |
2 |
Correct |
1 ms |
200 KB |
Output is correct |
3 |
Correct |
2 ms |
200 KB |
Output is correct |
4 |
Correct |
1 ms |
200 KB |
Output is correct |
5 |
Correct |
1 ms |
200 KB |
Output is correct |
6 |
Correct |
1 ms |
200 KB |
Output is correct |
7 |
Correct |
1 ms |
200 KB |
Output is correct |
8 |
Correct |
2 ms |
200 KB |
Output is correct |
9 |
Correct |
1 ms |
200 KB |
Output is correct |
10 |
Correct |
1 ms |
200 KB |
Output is correct |
11 |
Correct |
2 ms |
200 KB |
Output is correct |
12 |
Correct |
1 ms |
200 KB |
Output is correct |
13 |
Correct |
1 ms |
200 KB |
Output is correct |
14 |
Correct |
1 ms |
200 KB |
Output is correct |
15 |
Correct |
1 ms |
200 KB |
Output is correct |
16 |
Correct |
2 ms |
200 KB |
Output is correct |
17 |
Correct |
1 ms |
200 KB |
Output is correct |
18 |
Correct |
1 ms |
200 KB |
Output is correct |
19 |
Correct |
2 ms |
200 KB |
Output is correct |
20 |
Correct |
1 ms |
272 KB |
Output is correct |
21 |
Correct |
1 ms |
200 KB |
Output is correct |
22 |
Correct |
1 ms |
200 KB |
Output is correct |
23 |
Correct |
2 ms |
288 KB |
Output is correct |
24 |
Correct |
1 ms |
292 KB |
Output is correct |
25 |
Correct |
1 ms |
296 KB |
Output is correct |
26 |
Correct |
1 ms |
200 KB |
Output is correct |
27 |
Correct |
1 ms |
200 KB |
Output is correct |
28 |
Correct |
1 ms |
200 KB |
Output is correct |
29 |
Correct |
1 ms |
200 KB |
Output is correct |
30 |
Correct |
1 ms |
200 KB |
Output is correct |
31 |
Correct |
1 ms |
200 KB |
Output is correct |
32 |
Correct |
1 ms |
200 KB |
Output is correct |
33 |
Correct |
2 ms |
200 KB |
Output is correct |
34 |
Correct |
1 ms |
200 KB |
Output is correct |
35 |
Correct |
3 ms |
200 KB |
Output is correct |
36 |
Correct |
2 ms |
200 KB |
Output is correct |
37 |
Correct |
1 ms |
200 KB |
Output is correct |
38 |
Correct |
1 ms |
200 KB |
Output is correct |
39 |
Correct |
1 ms |
272 KB |
Output is correct |
40 |
Correct |
1 ms |
292 KB |
Output is correct |
41 |
Correct |
1 ms |
200 KB |
Output is correct |
42 |
Correct |
1 ms |
200 KB |
Output is correct |
43 |
Correct |
2 ms |
200 KB |
Output is correct |
44 |
Correct |
1 ms |
200 KB |
Output is correct |
45 |
Correct |
1 ms |
200 KB |
Output is correct |
46 |
Correct |
1 ms |
200 KB |
Output is correct |
47 |
Correct |
1 ms |
200 KB |
Output is correct |
48 |
Correct |
1 ms |
200 KB |
Output is correct |
49 |
Correct |
1 ms |
284 KB |
Output is correct |
50 |
Incorrect |
2 ms |
296 KB |
Incorrect |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
200 KB |
Output is correct |
2 |
Correct |
1 ms |
200 KB |
Output is correct |
3 |
Correct |
2 ms |
200 KB |
Output is correct |
4 |
Correct |
1 ms |
200 KB |
Output is correct |
5 |
Correct |
1 ms |
200 KB |
Output is correct |
6 |
Correct |
1 ms |
200 KB |
Output is correct |
7 |
Correct |
1 ms |
200 KB |
Output is correct |
8 |
Correct |
2 ms |
200 KB |
Output is correct |
9 |
Correct |
1 ms |
200 KB |
Output is correct |
10 |
Correct |
1 ms |
200 KB |
Output is correct |
11 |
Correct |
2 ms |
200 KB |
Output is correct |
12 |
Correct |
1 ms |
200 KB |
Output is correct |
13 |
Correct |
1 ms |
200 KB |
Output is correct |
14 |
Correct |
1 ms |
200 KB |
Output is correct |
15 |
Correct |
1 ms |
200 KB |
Output is correct |
16 |
Correct |
2 ms |
200 KB |
Output is correct |
17 |
Correct |
1 ms |
200 KB |
Output is correct |
18 |
Correct |
1 ms |
200 KB |
Output is correct |
19 |
Correct |
2 ms |
200 KB |
Output is correct |
20 |
Correct |
1 ms |
272 KB |
Output is correct |
21 |
Correct |
1 ms |
200 KB |
Output is correct |
22 |
Correct |
1 ms |
200 KB |
Output is correct |
23 |
Correct |
2 ms |
288 KB |
Output is correct |
24 |
Correct |
1 ms |
292 KB |
Output is correct |
25 |
Correct |
1 ms |
296 KB |
Output is correct |
26 |
Correct |
1 ms |
200 KB |
Output is correct |
27 |
Correct |
2 ms |
268 KB |
Output is correct |
28 |
Correct |
2 ms |
200 KB |
Output is correct |
29 |
Correct |
1 ms |
200 KB |
Output is correct |
30 |
Correct |
1 ms |
200 KB |
Output is correct |
31 |
Correct |
1 ms |
200 KB |
Output is correct |
32 |
Correct |
1 ms |
200 KB |
Output is correct |
33 |
Correct |
2 ms |
292 KB |
Output is correct |
34 |
Correct |
1 ms |
200 KB |
Output is correct |
35 |
Correct |
1 ms |
200 KB |
Output is correct |
36 |
Correct |
1 ms |
292 KB |
Output is correct |
37 |
Correct |
1 ms |
200 KB |
Output is correct |
38 |
Correct |
1 ms |
200 KB |
Output is correct |
39 |
Correct |
1 ms |
288 KB |
Output is correct |
40 |
Correct |
1 ms |
320 KB |
Output is correct |
41 |
Correct |
1 ms |
200 KB |
Output is correct |
42 |
Correct |
1 ms |
268 KB |
Output is correct |
43 |
Correct |
1 ms |
200 KB |
Output is correct |
44 |
Correct |
2 ms |
200 KB |
Output is correct |
45 |
Correct |
1 ms |
200 KB |
Output is correct |
46 |
Correct |
2 ms |
276 KB |
Output is correct |
47 |
Correct |
1 ms |
200 KB |
Output is correct |
48 |
Correct |
1 ms |
200 KB |
Output is correct |
49 |
Correct |
4 ms |
200 KB |
Output is correct |
50 |
Correct |
2 ms |
200 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
200 KB |
Output is correct |
2 |
Correct |
1 ms |
200 KB |
Output is correct |
3 |
Correct |
2 ms |
200 KB |
Output is correct |
4 |
Correct |
1 ms |
200 KB |
Output is correct |
5 |
Correct |
1 ms |
200 KB |
Output is correct |
6 |
Correct |
1 ms |
200 KB |
Output is correct |
7 |
Correct |
1 ms |
200 KB |
Output is correct |
8 |
Correct |
2 ms |
200 KB |
Output is correct |
9 |
Correct |
1 ms |
200 KB |
Output is correct |
10 |
Correct |
1 ms |
200 KB |
Output is correct |
11 |
Correct |
2 ms |
200 KB |
Output is correct |
12 |
Correct |
1 ms |
200 KB |
Output is correct |
13 |
Correct |
1 ms |
200 KB |
Output is correct |
14 |
Correct |
1 ms |
200 KB |
Output is correct |
15 |
Correct |
1 ms |
200 KB |
Output is correct |
16 |
Correct |
2 ms |
200 KB |
Output is correct |
17 |
Correct |
1 ms |
200 KB |
Output is correct |
18 |
Correct |
1 ms |
200 KB |
Output is correct |
19 |
Correct |
2 ms |
200 KB |
Output is correct |
20 |
Correct |
1 ms |
272 KB |
Output is correct |
21 |
Correct |
1 ms |
200 KB |
Output is correct |
22 |
Correct |
1 ms |
200 KB |
Output is correct |
23 |
Correct |
2 ms |
288 KB |
Output is correct |
24 |
Correct |
1 ms |
292 KB |
Output is correct |
25 |
Correct |
1 ms |
296 KB |
Output is correct |
26 |
Correct |
1 ms |
200 KB |
Output is correct |
27 |
Correct |
1 ms |
200 KB |
Output is correct |
28 |
Correct |
1 ms |
200 KB |
Output is correct |
29 |
Correct |
1 ms |
200 KB |
Output is correct |
30 |
Correct |
1 ms |
200 KB |
Output is correct |
31 |
Correct |
1 ms |
200 KB |
Output is correct |
32 |
Correct |
1 ms |
200 KB |
Output is correct |
33 |
Correct |
2 ms |
200 KB |
Output is correct |
34 |
Correct |
1 ms |
200 KB |
Output is correct |
35 |
Correct |
3 ms |
200 KB |
Output is correct |
36 |
Correct |
2 ms |
200 KB |
Output is correct |
37 |
Correct |
1 ms |
200 KB |
Output is correct |
38 |
Correct |
1 ms |
200 KB |
Output is correct |
39 |
Correct |
1 ms |
272 KB |
Output is correct |
40 |
Correct |
1 ms |
292 KB |
Output is correct |
41 |
Correct |
1 ms |
200 KB |
Output is correct |
42 |
Correct |
1 ms |
200 KB |
Output is correct |
43 |
Correct |
2 ms |
200 KB |
Output is correct |
44 |
Correct |
1 ms |
200 KB |
Output is correct |
45 |
Correct |
1 ms |
200 KB |
Output is correct |
46 |
Correct |
1 ms |
200 KB |
Output is correct |
47 |
Correct |
1 ms |
200 KB |
Output is correct |
48 |
Correct |
1 ms |
200 KB |
Output is correct |
49 |
Correct |
1 ms |
284 KB |
Output is correct |
50 |
Incorrect |
2 ms |
296 KB |
Incorrect |