import java.util.HashMap;
public class biscuits {
long count_tastiness(long x, long[] a) {
@SuppressWarnings({"unchecked", "rawtypes"})
HashMap<Long, Long>[] freqs = new HashMap[] { new HashMap(), new HashMap() };
freqs[0].put(a[0], 1l);
return recursiveFaster(0, freqs, 0, a, x);
}
long recursiveFaster(int pos, HashMap<Long, Long>[] freqs, int par, long[] a, long x) {
//System.out.println(pos + ": " + freq);
if (pos == a.length - 1) {
long ans = 0;
for (long y : freqs[par].keySet()) {
ans += freqs[par].get(y) * (y / x + 1);
}
return ans;
}
if (freqs[par].size() > x + 1) {
System.exit(3);
}
freqs[par^1].clear();
for (long y : freqs[par].keySet()) {
long val = a[pos + 1] + y / 2;
if (!freqs[par^1].containsKey(val)) freqs[par^1].put(val, 0l);
freqs[par^1].put(val, freqs[par^1].get(val) + freqs[par].get(y));
if (y >= x) {
val = a[pos + 1] + (y - x) / 2;
if (!freqs[par^1].containsKey(val)) freqs[par^1].put(val, 0l);
freqs[par^1].put(val, freqs[par^1].get(val) + freqs[par].get(y));
}
}
return recursiveFaster(pos + 1, freqs, (par ^ 1), a, x);
}
long recursiveForOne(int pos, long l, long r, HashMap<Long, Long> freq, long[] a) {
if (pos == a.length - 1) {
long ans = 0;
for (long y = l; y <= r; y++) {
ans += freq.get(y) * (y + 1);
}
return ans;
}
// for each l <= y <= r: a[pos + 1] + y/2 and (y-1)/2
long min = Long.MAX_VALUE;
for (long y = l; y <= r; y++) {
min = Math.min(min, a[pos + 1] + y/2);
if (y > 0) {
min = Math.min(min, a[pos + 1] + (y-1)/2);
}
}
long max = Long.MIN_VALUE;
for (long y = l; y <= r; y++) {
max = Math.max(max, a[pos + 1] + y/2);
}
HashMap<Long, Long> map = new HashMap<>();
for (long y = l; y <= r; y++) {
long val = a[pos + 1] + y / 2;
if (!map.containsKey(val)) map.put(val, 0l);
map.put(val, map.get(val) + freq.getOrDefault(y, 0l));
if (y > 0) {
val = a[pos + 1] + (y - 1) / 2;
if (!map.containsKey(val)) map.put(val, 0l);
map.put(val, map.get(val) + freq.getOrDefault(y, 0l));
}
}
return recursiveForOne(pos + 1, min, max, map, a);
}
long countNaive(long x, long[] a) {
return countRec(x, a, 0);
}
long countRec(long x, long[] a, int index) {
if (index == a.length - 1) {
return a[a.length - 1] / x + 1;
}
long temp = a[index + 1];
a[index + 1] = a[index + 1] + a[index] / 2;
long answer = countRec(x, a, index + 1);
if (a[index] >= x) {
a[index + 1] = temp + (a[index] - x) / 2;
answer += countRec(x, a, index + 1);
a[index + 1] = temp;
}
a[index + 1] = temp;
return answer;
}
}
// (s[k-1] - i * X) / (2^(k-1)), 0 <= i < 2^(k - 1).
// For which i is this state valid?
// If for each position b s.t. b-th bit is set in i, (s[b+1] - (2^b + prev(i,b))X) / 2^(b+1) >= X.
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
91 ms |
10140 KB |
Output is correct |
2 |
Correct |
96 ms |
10296 KB |
Output is correct |
3 |
Correct |
86 ms |
10072 KB |
Output is correct |
4 |
Correct |
84 ms |
10256 KB |
Output is correct |
5 |
Correct |
86 ms |
10200 KB |
Output is correct |
6 |
Correct |
97 ms |
10432 KB |
Output is correct |
7 |
Correct |
86 ms |
10316 KB |
Output is correct |
8 |
Correct |
104 ms |
10320 KB |
Output is correct |
9 |
Correct |
89 ms |
10284 KB |
Output is correct |
10 |
Correct |
89 ms |
10288 KB |
Output is correct |
11 |
Correct |
94 ms |
10284 KB |
Output is correct |
12 |
Correct |
115 ms |
10640 KB |
Output is correct |
13 |
Correct |
108 ms |
10860 KB |
Output is correct |
14 |
Correct |
141 ms |
13036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
101 ms |
10424 KB |
Output is correct |
2 |
Correct |
95 ms |
10324 KB |
Output is correct |
3 |
Correct |
87 ms |
10184 KB |
Output is correct |
4 |
Correct |
91 ms |
10236 KB |
Output is correct |
5 |
Correct |
94 ms |
10400 KB |
Output is correct |
6 |
Correct |
107 ms |
11308 KB |
Output is correct |
7 |
Correct |
87 ms |
10548 KB |
Output is correct |
8 |
Correct |
116 ms |
10588 KB |
Output is correct |
9 |
Correct |
108 ms |
10572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
101 ms |
10596 KB |
Output is correct |
2 |
Correct |
106 ms |
10292 KB |
Output is correct |
3 |
Correct |
85 ms |
10256 KB |
Output is correct |
4 |
Correct |
99 ms |
10548 KB |
Output is correct |
5 |
Correct |
106 ms |
10884 KB |
Output is correct |
6 |
Correct |
126 ms |
12064 KB |
Output is correct |
7 |
Correct |
100 ms |
10044 KB |
Output is correct |
8 |
Execution timed out |
1105 ms |
91844 KB |
Time limit exceeded |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
124 ms |
11460 KB |
Output is correct |
2 |
Execution timed out |
1147 ms |
76832 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
91 ms |
10140 KB |
Output is correct |
2 |
Correct |
96 ms |
10296 KB |
Output is correct |
3 |
Correct |
86 ms |
10072 KB |
Output is correct |
4 |
Correct |
84 ms |
10256 KB |
Output is correct |
5 |
Correct |
86 ms |
10200 KB |
Output is correct |
6 |
Correct |
97 ms |
10432 KB |
Output is correct |
7 |
Correct |
86 ms |
10316 KB |
Output is correct |
8 |
Correct |
104 ms |
10320 KB |
Output is correct |
9 |
Correct |
89 ms |
10284 KB |
Output is correct |
10 |
Correct |
89 ms |
10288 KB |
Output is correct |
11 |
Correct |
94 ms |
10284 KB |
Output is correct |
12 |
Correct |
115 ms |
10640 KB |
Output is correct |
13 |
Correct |
108 ms |
10860 KB |
Output is correct |
14 |
Correct |
141 ms |
13036 KB |
Output is correct |
15 |
Correct |
101 ms |
10424 KB |
Output is correct |
16 |
Correct |
95 ms |
10324 KB |
Output is correct |
17 |
Correct |
87 ms |
10184 KB |
Output is correct |
18 |
Correct |
91 ms |
10236 KB |
Output is correct |
19 |
Correct |
94 ms |
10400 KB |
Output is correct |
20 |
Correct |
107 ms |
11308 KB |
Output is correct |
21 |
Correct |
87 ms |
10548 KB |
Output is correct |
22 |
Correct |
116 ms |
10588 KB |
Output is correct |
23 |
Correct |
108 ms |
10572 KB |
Output is correct |
24 |
Correct |
101 ms |
10596 KB |
Output is correct |
25 |
Correct |
106 ms |
10292 KB |
Output is correct |
26 |
Correct |
85 ms |
10256 KB |
Output is correct |
27 |
Correct |
99 ms |
10548 KB |
Output is correct |
28 |
Correct |
106 ms |
10884 KB |
Output is correct |
29 |
Correct |
126 ms |
12064 KB |
Output is correct |
30 |
Correct |
100 ms |
10044 KB |
Output is correct |
31 |
Execution timed out |
1105 ms |
91844 KB |
Time limit exceeded |
32 |
Halted |
0 ms |
0 KB |
- |