oj.uz

Submission #305878

# Submission time Handle Problem Language Result Execution time Memory
305878 2020-09-24T04:10:36 Z llaki Packing Biscuits (IOI20_biscuits) Java 11
21 / 100
 1000 ms 107688 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;
        }
        if (freq.size() > 2 * x) {
            System.exit(3);
        }
        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 87 ms 10360 KB Output is correct
2 Correct 96 ms 10420 KB Output is correct
3 Correct 92 ms 10252 KB Output is correct
4 Correct 91 ms 10352 KB Output is correct
5 Correct 85 ms 10356 KB Output is correct
6 Correct 90 ms 10484 KB Output is correct
7 Correct 86 ms 10228 KB Output is correct
8 Correct 99 ms 10360 KB Output is correct
9 Correct 89 ms 10240 KB Output is correct
10 Correct 94 ms 10340 KB Output is correct
11 Correct 90 ms 10160 KB Output is correct
12 Correct 99 ms 10596 KB Output is correct
13 Correct 112 ms 11080 KB Output is correct
14 Correct 119 ms 11760 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 10548 KB Output is correct
2 Correct 92 ms 10500 KB Output is correct
3 Correct 91 ms 10352 KB Output is correct
4 Correct 94 ms 10472 KB Output is correct
5 Correct 97 ms 10480 KB Output is correct
6 Correct 110 ms 11372 KB Output is correct
7 Correct 87 ms 10216 KB Output is correct
8 Correct 102 ms 10876 KB Output is correct
9 Correct 101 ms 10988 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 10864 KB Output is correct
2 Correct 90 ms 10304 KB Output is correct
3 Correct 87 ms 10356 KB Output is correct
4 Correct 106 ms 10484 KB Output is correct
5 Correct 105 ms 10772 KB Output is correct
6 Correct 129 ms 12516 KB Output is correct
7 Correct 91 ms 10236 KB Output is correct
8 Execution timed out 1042 ms 98016 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 11524 KB Output is correct
2 Execution timed out 1097 ms 107688 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 10360 KB Output is correct
2 Correct 96 ms 10420 KB Output is correct
3 Correct 92 ms 10252 KB Output is correct
4 Correct 91 ms 10352 KB Output is correct
5 Correct 85 ms 10356 KB Output is correct
6 Correct 90 ms 10484 KB Output is correct
7 Correct 86 ms 10228 KB Output is correct
8 Correct 99 ms 10360 KB Output is correct
9 Correct 89 ms 10240 KB Output is correct
10 Correct 94 ms 10340 KB Output is correct
11 Correct 90 ms 10160 KB Output is correct
12 Correct 99 ms 10596 KB Output is correct
13 Correct 112 ms 11080 KB Output is correct
14 Correct 119 ms 11760 KB Output is correct
15 Correct 88 ms 10548 KB Output is correct
16 Correct 92 ms 10500 KB Output is correct
17 Correct 91 ms 10352 KB Output is correct
18 Correct 94 ms 10472 KB Output is correct
19 Correct 97 ms 10480 KB Output is correct
20 Correct 110 ms 11372 KB Output is correct
21 Correct 87 ms 10216 KB Output is correct
22 Correct 102 ms 10876 KB Output is correct
23 Correct 101 ms 10988 KB Output is correct
24 Correct 103 ms 10864 KB Output is correct
25 Correct 90 ms 10304 KB Output is correct
26 Correct 87 ms 10356 KB Output is correct
27 Correct 106 ms 10484 KB Output is correct
28 Correct 105 ms 10772 KB Output is correct
29 Correct 129 ms 12516 KB Output is correct
30 Correct 91 ms 10236 KB Output is correct
31 Execution timed out 1042 ms 98016 KB Time limit exceeded
32 Halted 0 ms 0 KB -