Submission #305908

#	Time	Username	Problem	Language	Result	Execution time	Memory
305908		llaki	Packing Biscuits (IOI20_biscuits)	Java	0 / 100	111 ms	11508 KiB

biscuits

import java.util.HashMap;

public class biscuits {
    long count_tastiness(long x, long[] a) {
        HashMap<Long, Long>[] freqs = new HashMap[] { new HashMap(), new HashMap() };
        freqs[0].put(a[0], 1l);
        return recursiveFaster(0, freqs, 1, 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.

Compilation message (stderr)

Note: biscuits.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 21
• Subtask 4: 0 / 35
• Subtask 5: 0 / 23