// moreflags=grader.cpp
// ......
#include "biscuits.h"
#include<array>
#include<cstdint>
#include<vector>
#include<cmath>
#include<iostream>
#if not LOCAL
#define NDEBUG
#endif
#include<cassert>
struct Node{ // represents a non-strictly decreasing list of numbers
int64_t count;
int64_t first; // also the maximum
int64_t delta;
std::array<int, 2> children; // index in nodes vector, or {{-1, -1}} if count==1
};
std::vector<Node> nodes;
int deltaed(int node, int64_t delta){
if(node<0 or delta==0) return node;
nodes.push_back(nodes[node]);
nodes.back().first+=delta;
nodes.back().delta+=delta;
return int(nodes.size()-1);
}
int append(int first, int sec, int64_t delta){
assert(first>=0); // precondition
if(sec==-1) return deltaed(first, delta);
assert(sec>=0);
nodes.push_back({
nodes[first].count+nodes[sec].count,
nodes[first].first+delta,
delta,
{{first, sec}}
});
return int(nodes.size()-1);
}
int prefixLargerEqual(int node, int64_t minimum){
// return -1 if result is empty
assert((nodes[node].count==1)==(nodes[node].children==std::array<int, 2>{{-1, -1}}));
if(nodes[node].first<minimum) return -1;
if(nodes[node].count==1){
// single node
assert(nodes[node].first==nodes[node].delta);
return node;
}
auto const [a, b]=nodes[node].children;
auto const t=minimum-nodes[node].delta;
auto const b1=prefixLargerEqual(b, t);
if(b1==b) return node;
if(b1<0) return deltaed(prefixLargerEqual(a, t), nodes[node].delta);
return append(a, b1, nodes[node].delta);
}
long long count_tastiness(long long x, std::vector<long long> a) {
nodes.clear();
nodes.push_back({1, a[0], a[0], {{-1, -1}}});
int all=0; // node reference
// initial list: {a[0]} (note that the first element will always be a[0])
int64_t s=0;
for(int i=0;; ++i){
assert(nodes[all].first==a[0]);
if(a[0]-x*std::round(std::pow(2., i))>=s){
all=append(all, deltaed(prefixLargerEqual(all, s+(x<<i)), -(x<<i)), 0);
}
if(i+1<(int)a.size())
s-=a[i+1]<<(i+1);
if(i==(int)a.size()+62){
return nodes[all].count;
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
256 KB |
Output is correct |
5 |
Correct |
1 ms |
256 KB |
Output is correct |
6 |
Correct |
1 ms |
256 KB |
Output is correct |
7 |
Correct |
1 ms |
256 KB |
Output is correct |
8 |
Correct |
1 ms |
256 KB |
Output is correct |
9 |
Correct |
0 ms |
256 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
256 KB |
Output is correct |
12 |
Correct |
1 ms |
256 KB |
Output is correct |
13 |
Correct |
1 ms |
256 KB |
Output is correct |
14 |
Correct |
1 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
256 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
256 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
256 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
384 KB |
Output is correct |
2 |
Correct |
25 ms |
896 KB |
Output is correct |
3 |
Correct |
23 ms |
896 KB |
Output is correct |
4 |
Correct |
23 ms |
888 KB |
Output is correct |
5 |
Correct |
24 ms |
896 KB |
Output is correct |
6 |
Correct |
23 ms |
896 KB |
Output is correct |
7 |
Correct |
23 ms |
896 KB |
Output is correct |
8 |
Correct |
24 ms |
896 KB |
Output is correct |
9 |
Correct |
22 ms |
896 KB |
Output is correct |
10 |
Correct |
22 ms |
896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
256 KB |
Output is correct |
5 |
Correct |
1 ms |
256 KB |
Output is correct |
6 |
Correct |
1 ms |
256 KB |
Output is correct |
7 |
Correct |
1 ms |
256 KB |
Output is correct |
8 |
Correct |
1 ms |
256 KB |
Output is correct |
9 |
Correct |
0 ms |
256 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
256 KB |
Output is correct |
12 |
Correct |
1 ms |
256 KB |
Output is correct |
13 |
Correct |
1 ms |
256 KB |
Output is correct |
14 |
Correct |
1 ms |
256 KB |
Output is correct |
15 |
Correct |
0 ms |
256 KB |
Output is correct |
16 |
Correct |
1 ms |
256 KB |
Output is correct |
17 |
Correct |
1 ms |
256 KB |
Output is correct |
18 |
Correct |
1 ms |
384 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
1 ms |
384 KB |
Output is correct |
21 |
Correct |
1 ms |
384 KB |
Output is correct |
22 |
Correct |
1 ms |
384 KB |
Output is correct |
23 |
Correct |
1 ms |
384 KB |
Output is correct |
24 |
Correct |
1 ms |
384 KB |
Output is correct |
25 |
Correct |
1 ms |
256 KB |
Output is correct |
26 |
Correct |
1 ms |
256 KB |
Output is correct |
27 |
Correct |
1 ms |
256 KB |
Output is correct |
28 |
Correct |
1 ms |
384 KB |
Output is correct |
29 |
Correct |
1 ms |
384 KB |
Output is correct |
30 |
Correct |
1 ms |
256 KB |
Output is correct |
31 |
Correct |
1 ms |
384 KB |
Output is correct |
32 |
Correct |
1 ms |
256 KB |
Output is correct |
33 |
Correct |
1 ms |
384 KB |
Output is correct |
34 |
Correct |
1 ms |
384 KB |
Output is correct |
35 |
Correct |
1 ms |
384 KB |
Output is correct |
36 |
Correct |
1 ms |
384 KB |
Output is correct |
37 |
Correct |
8 ms |
384 KB |
Output is correct |
38 |
Correct |
25 ms |
896 KB |
Output is correct |
39 |
Correct |
23 ms |
896 KB |
Output is correct |
40 |
Correct |
23 ms |
888 KB |
Output is correct |
41 |
Correct |
24 ms |
896 KB |
Output is correct |
42 |
Correct |
23 ms |
896 KB |
Output is correct |
43 |
Correct |
23 ms |
896 KB |
Output is correct |
44 |
Correct |
24 ms |
896 KB |
Output is correct |
45 |
Correct |
22 ms |
896 KB |
Output is correct |
46 |
Correct |
22 ms |
896 KB |
Output is correct |
47 |
Correct |
10 ms |
384 KB |
Output is correct |
48 |
Correct |
33 ms |
896 KB |
Output is correct |
49 |
Correct |
14 ms |
384 KB |
Output is correct |
50 |
Correct |
29 ms |
768 KB |
Output is correct |
51 |
Correct |
24 ms |
888 KB |
Output is correct |
52 |
Correct |
7 ms |
384 KB |
Output is correct |
53 |
Correct |
20 ms |
896 KB |
Output is correct |
54 |
Correct |
30 ms |
896 KB |
Output is correct |
55 |
Correct |
30 ms |
896 KB |
Output is correct |
56 |
Correct |
28 ms |
896 KB |
Output is correct |
57 |
Correct |
28 ms |
896 KB |
Output is correct |