/**
* Binary. Hmm, interesting. I started with [S2], which I solved with recursion in
* O(kq). The basic idea is to treat two 2^i biscuits in the bag as one 2^(i+1).
*
* A few greedy observations:
* (1) Given x, can we determine if it's possible? Well, we can simply iterate i
* from large to small. If the additional tastiness x we still need for a
* certain bag satisfies x >= 2^i, put a biscuit 2^i in the bag if there's one.
* (2) Biscuits of the same type can be distributed as evenly as possible, i.e.
* there is an optimal partition s.t. for every i
* |#2^i_biscuits_in_bag_1 - #2^i_biscuits_in_big_2| <= 1.
* (3) Unlike (1), (2), we consider from small to large. If x is odd, each bag needs
* at least 1 2^0 biscuit. After that, every 2 2^O biscuits can be grouped to
* form 1 2^1 biscuit, so we can add this num to the original num of 2^1
* biscuits. Well, let's write this recursively:
* def find():
* total = 0
* if #2^0 >= x:
* add floor((#2^0 - x) / 2) to #2^1 and recurse downdwards
* add floor(#2^0 / 2) to 2^1 and recurse downwards
* ...
*
* Can we AC this problem with (3)? I guess that the num of configurations given to
* find() isn't too many, so we can optimize it with memoization. Indeed, we can
* prove that in each level of find(), the num. of unique calls the next level of
* find() is bounded by x. This is because x >= x/2 + x/4 + x/8 + x/16 + .... [S1-3]
* are solved.
*
* In impl1, the function search(p, first) doesn't decrease as first increases.
* Furthermore, if search(p, w) and search(p, z) are both called, |w-z| <= x. (For
* each p, the val first only varies in a range with len <= x.) Next, one can prove
* that within this range search() can take at most 3 distinct values (by induction).
* We can binary search for the largest / smallest value for first that attains a
* certain search(p, ..).
*
* Time Complexity: O(kq * log(x) * log(k))
* Implementation 1.5 (Full solution (?!), greedy + binary search + maths)
*/
#include <bits/stdc++.h>
#include "biscuits.h"
typedef long long ll;
ll wrap(int p, ll first); // wraper function for search()
ll search(int p, ll first);
ll x;
std::vector<ll> a;
std::vector<std::map<ll, ll>> cache1;
std::vector<std::map<ll, ll, std::greater<ll>>> cache2;
ll wrap(int p, ll first) {
auto v1 = cache1[p].lower_bound(first);
auto v2 = cache2[p].lower_bound(first);
if (v1 != cache1[p].end() && v2 != cache2[p].end()) {
if (v1->second == v2->second)
return v1->second;
}
ll val = search(p, first);
ll high = first, low = first;
for (ll step = x / 2 + 1; step >= 1; step /= 2) {
while (search(p, high + step) == val)
high += step;
while (low - step >= 0 && search(p, low - step) == val)
low -= step;
}
cache1[p][high] = cache2[p][low] = val;
return val;
}
ll search(int p, ll first) {
int k = a.size();
if (p == k - 1)
return first / x + 1;
ll total = wrap(p + 1, a[p + 1] + first / 2);
if (first >= x)
total += wrap(p + 1, a[p + 1] + (first - x) / 2);
return total;
}
ll count_tastiness(ll _x, std::vector<ll> _a) {
x = _x, a = _a;
int k = _a.size();
cache1.assign(k, std::map<ll, ll>());
cache2.assign(k, std::map<ll, ll, std::greater<ll>>());
return wrap(0, a[0]);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
3 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
3 ms |
340 KB |
Output is correct |
11 |
Correct |
8 ms |
384 KB |
Output is correct |
12 |
Correct |
13 ms |
340 KB |
Output is correct |
13 |
Correct |
14 ms |
392 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
663 ms |
872 KB |
Output is correct |
3 |
Correct |
636 ms |
1324 KB |
Output is correct |
4 |
Correct |
611 ms |
1236 KB |
Output is correct |
5 |
Correct |
574 ms |
1236 KB |
Output is correct |
6 |
Correct |
824 ms |
1200 KB |
Output is correct |
7 |
Correct |
862 ms |
1212 KB |
Output is correct |
8 |
Correct |
804 ms |
1200 KB |
Output is correct |
9 |
Correct |
789 ms |
1216 KB |
Output is correct |
10 |
Correct |
555 ms |
1324 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
212 KB |
Output is correct |
24 |
Correct |
0 ms |
212 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
0 ms |
212 KB |
Output is correct |
27 |
Correct |
1 ms |
212 KB |
Output is correct |
28 |
Correct |
0 ms |
212 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
0 ms |
212 KB |
Output is correct |
31 |
Correct |
3 ms |
340 KB |
Output is correct |
32 |
Correct |
0 ms |
212 KB |
Output is correct |
33 |
Correct |
3 ms |
340 KB |
Output is correct |
34 |
Correct |
8 ms |
384 KB |
Output is correct |
35 |
Correct |
13 ms |
340 KB |
Output is correct |
36 |
Correct |
14 ms |
392 KB |
Output is correct |
37 |
Correct |
1 ms |
340 KB |
Output is correct |
38 |
Correct |
663 ms |
872 KB |
Output is correct |
39 |
Correct |
636 ms |
1324 KB |
Output is correct |
40 |
Correct |
611 ms |
1236 KB |
Output is correct |
41 |
Correct |
574 ms |
1236 KB |
Output is correct |
42 |
Correct |
824 ms |
1200 KB |
Output is correct |
43 |
Correct |
862 ms |
1212 KB |
Output is correct |
44 |
Correct |
804 ms |
1200 KB |
Output is correct |
45 |
Correct |
789 ms |
1216 KB |
Output is correct |
46 |
Correct |
555 ms |
1324 KB |
Output is correct |
47 |
Correct |
2 ms |
340 KB |
Output is correct |
48 |
Correct |
58 ms |
1332 KB |
Output is correct |
49 |
Correct |
2 ms |
312 KB |
Output is correct |
50 |
Correct |
46 ms |
1176 KB |
Output is correct |
51 |
Correct |
99 ms |
1328 KB |
Output is correct |
52 |
Correct |
5 ms |
340 KB |
Output is correct |
53 |
Correct |
77 ms |
1168 KB |
Output is correct |
54 |
Execution timed out |
1045 ms |
1236 KB |
Time limit exceeded |
55 |
Halted |
0 ms |
0 KB |
- |