oj.uz

Submission #305871

# Submission time Handle Problem Language Result Execution time Memory
305871 2020-09-24T03:57:17 Z llaki Packing Biscuits (IOI20_biscuits) Java 11
21 / 100
 1000 ms 116688 KB 
import java.util.HashMap;

public class biscuits {
    long count_tastiness(long x, long[] a) {
        if (x == 1) {
            return solveXIsOne(a);
        }
        HashMap<Long, Long> freq = new HashMap<>();
        freq.put(a[0], 1l);
        return recursiveFaster(0, freq, a, x);
        //return countNaive(x, a);
    }

    // How many diff. sums can we get by  (n[i] * 2^i, where 0 <= n[i] <= a[i]).
    long solveXIsOne(long[] a) {
        HashMap<Long, Long> freq = new HashMap<>();
        freq.put(a[0], 1l);
        return recursiveForOne(0, a[0], a[0], freq, a);
        //return recursiveXIsOne(0, a[0], a);
    }

    HashMap<String, Long> map = new HashMap<>();

    String toKey(int pos, long first) {
        return pos + "." + first;
    }

    long recursiveXIsOne(int pos, long first, long[] a) {
        if (pos == a.length - 1) {
            return first + 1;
        }
        String key = toKey(pos, first);
        if (map.containsKey(key)) map.get(key);
        long res = recursiveXIsOne(pos + 1, a[pos + 1] + first / 2, a);
        if (first > 0) {
            res += recursiveXIsOne(pos + 1, a[pos + 1] + (first - 1) / 2, a);
        }
        map.put(key, res);
        return res;
    }

    long recursiveFaster(int pos, HashMap<Long, Long> freq, long[] a, long x) {
        //System.out.println(pos + ": " + freq);
        if (pos == a.length - 1) {
            long ans = 0;
            for (long y : freq.keySet()) {
                ans += freq.get(y) * (y / x + 1);
            }
            return ans;
        }
        HashMap<Long, Long> map = new HashMap<>();
        // for each y in freq.keyset(): a[pos + 1] + y/2 and (y-1)/2.
        for (long y : freq.keySet()) {
            long val = a[pos + 1] + y / 2;
            if (!map.containsKey(val)) map.put(val, 0l);
            map.put(val, map.get(val) + freq.get(y));
            if (y >= x) {
                val = a[pos + 1] + (y - x) / 2;
                if (!map.containsKey(val)) map.put(val, 0l);
                map.put(val, map.get(val) + freq.get(y));
            }
        }
        return recursiveFaster(pos + 1, map, 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.

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 10488 KB Output is correct
2 Correct 92 ms 10344 KB Output is correct
3 Correct 85 ms 10360 KB Output is correct
4 Correct 86 ms 10484 KB Output is correct
5 Correct 86 ms 10136 KB Output is correct
6 Correct 91 ms 10476 KB Output is correct
7 Correct 81 ms 10616 KB Output is correct
8 Correct 98 ms 10360 KB Output is correct
9 Correct 89 ms 10296 KB Output is correct
10 Correct 93 ms 10364 KB Output is correct
11 Correct 84 ms 10484 KB Output is correct
12 Correct 103 ms 10908 KB Output is correct
13 Correct 111 ms 10896 KB Output is correct
14 Correct 147 ms 13548 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 10232 KB Output is correct
2 Correct 92 ms 10460 KB Output is correct
3 Correct 87 ms 10096 KB Output is correct
4 Correct 90 ms 10316 KB Output is correct
5 Correct 98 ms 10360 KB Output is correct
6 Correct 112 ms 11676 KB Output is correct
7 Correct 83 ms 10472 KB Output is correct
8 Correct 103 ms 11376 KB Output is correct
9 Correct 108 ms 10896 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 10368 KB Output is correct
2 Correct 83 ms 10248 KB Output is correct
3 Correct 84 ms 10392 KB Output is correct
4 Correct 102 ms 10632 KB Output is correct
5 Correct 101 ms 10740 KB Output is correct
6 Correct 127 ms 12516 KB Output is correct
7 Correct 91 ms 10340 KB Output is correct
8 Execution timed out 1083 ms 98964 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 11296 KB Output is correct
2 Execution timed out 1176 ms 116688 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 10488 KB Output is correct
2 Correct 92 ms 10344 KB Output is correct
3 Correct 85 ms 10360 KB Output is correct
4 Correct 86 ms 10484 KB Output is correct
5 Correct 86 ms 10136 KB Output is correct
6 Correct 91 ms 10476 KB Output is correct
7 Correct 81 ms 10616 KB Output is correct
8 Correct 98 ms 10360 KB Output is correct
9 Correct 89 ms 10296 KB Output is correct
10 Correct 93 ms 10364 KB Output is correct
11 Correct 84 ms 10484 KB Output is correct
12 Correct 103 ms 10908 KB Output is correct
13 Correct 111 ms 10896 KB Output is correct
14 Correct 147 ms 13548 KB Output is correct
15 Correct 86 ms 10232 KB Output is correct
16 Correct 92 ms 10460 KB Output is correct
17 Correct 87 ms 10096 KB Output is correct
18 Correct 90 ms 10316 KB Output is correct
19 Correct 98 ms 10360 KB Output is correct
20 Correct 112 ms 11676 KB Output is correct
21 Correct 83 ms 10472 KB Output is correct
22 Correct 103 ms 11376 KB Output is correct
23 Correct 108 ms 10896 KB Output is correct
24 Correct 104 ms 10368 KB Output is correct
25 Correct 83 ms 10248 KB Output is correct
26 Correct 84 ms 10392 KB Output is correct
27 Correct 102 ms 10632 KB Output is correct
28 Correct 101 ms 10740 KB Output is correct
29 Correct 127 ms 12516 KB Output is correct
30 Correct 91 ms 10340 KB Output is correct
31 Execution timed out 1083 ms 98964 KB Time limit exceeded
32 Halted 0 ms 0 KB -