#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
vector<long long> trans(const vector<long long>& a, long long sub) {
vector<long long> na = a;
na.pop_back();
if (a.back() - sub > 1) {
long long val = (a.back() - sub) / 2;
if (na.size() == 0) na.push_back(val);
else na.back() += val;
}
return na;
}
map<pair<int, long long>, long long> f;
long long solve(long long x, vector<long long> a, int pos) {
if (a.size() == 0) return 1;
if (f.count({pos, a.back()})) return f[{pos, a.back()}];
long long ret = 0;
if (a.back() >= x) {
ret += solve(x, trans(a, x), pos + 1);
}
ret += solve(x, trans(a, 0), pos + 1);
return f[{pos, a.back()}] = ret;
}
vector<long long> arr;
long long solve2(long long x, long long last, int pos) {
if ((int) arr.size() <= pos && last < x) return 1;
if (f.count({pos, last})) return f[{pos, last}];
long long ret = 0;
if (last >= x) {
long long nlast = (pos + 1 < (int) arr.size() ? arr[pos + 1] : 0) + (last - x) / 2;
ret += solve2(x, nlast, pos + 1);
}
long long nlast = (pos + 1 < (int) arr.size() ? arr[pos + 1] : 0) + last / 2;
ret += solve2(x, nlast, pos + 1);
return f[{pos, last}] = ret;
}
vector<long long> sums;
long long solve3(long long x, int pos, long long sub) {
if (pos == -1) return sub == 0;
long long cur = pos < (int) arr.size() ? arr[pos] : 0;
long long ret = 0;
if ((1LL << pos) <= (sums[pos] - sub) / x) {
long long what = solve3(x, pos - 1, max(0LL, sub + x * (1LL << pos) - (1LL << pos) * cur));
ret += what;
if (what == (1LL << pos)) {
ret += what;
return ret;
}
}
ret += solve3(x, pos - 1, max(0LL, sub - (1LL << pos) * cur));
return ret;
}
long long count_tastiness(long long x, vector<long long> a) {
f.clear(); sums.clear();
// for (int i = 0; i < (int) a.size(); ++i) {
// if (a[i] > x) {
// long long add = (a[i] - x) / 2;
// a[i] = x + ((a[i] - x) & 1);
// if (i + 1 == (int) a.size())
// a.push_back(add);
// else
// a[i + 1] += add;
// }
// }
long long s = 0, pw = 1;
for (int i = 0; i < 60; ++i) {
if (i < (int) a.size())
s += pw * a[i];
pw <<= 1;
sums.push_back(s);
}
// reverse(a.begin(), a.end());
arr = a;
// return solve2(x, arr[0], 0);
// cout << "2: " << solve2(x, arr[0], 0) << endl;
return solve3(x, 59, 0);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
0 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 |
0 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 |
0 ms |
256 KB |
Output is correct |
9 |
Correct |
0 ms |
256 KB |
Output is correct |
10 |
Correct |
0 ms |
256 KB |
Output is correct |
11 |
Correct |
0 ms |
256 KB |
Output is correct |
12 |
Correct |
2 ms |
276 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 |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
0 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 |
Execution timed out |
1099 ms |
256 KB |
Time limit exceeded |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
Execution timed out |
1090 ms |
256 KB |
Time limit exceeded |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Execution timed out |
1085 ms |
896 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
0 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 |
0 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 |
0 ms |
256 KB |
Output is correct |
9 |
Correct |
0 ms |
256 KB |
Output is correct |
10 |
Correct |
0 ms |
256 KB |
Output is correct |
11 |
Correct |
0 ms |
256 KB |
Output is correct |
12 |
Correct |
2 ms |
276 KB |
Output is correct |
13 |
Correct |
1 ms |
256 KB |
Output is correct |
14 |
Correct |
1 ms |
256 KB |
Output is correct |
15 |
Correct |
1 ms |
256 KB |
Output is correct |
16 |
Correct |
0 ms |
256 KB |
Output is correct |
17 |
Correct |
1 ms |
256 KB |
Output is correct |
18 |
Correct |
1 ms |
256 KB |
Output is correct |
19 |
Correct |
1 ms |
256 KB |
Output is correct |
20 |
Correct |
1 ms |
256 KB |
Output is correct |
21 |
Correct |
1 ms |
256 KB |
Output is correct |
22 |
Correct |
1 ms |
256 KB |
Output is correct |
23 |
Execution timed out |
1099 ms |
256 KB |
Time limit exceeded |