Submission #303084

#	Time	Username	Problem	Language	Result	Execution time	Memory
303084		llaki	Carnival Tickets (IOI20_tickets)	Java	100 / 100	2581 ms	118840 KiB

tickets

import java.util.Arrays;
import java.util.PriorityQueue;

public class tickets {
    long find_maximum(int k, int[][] x) {
        int n = x.length;
        int m = x[0].length;
        int[][] answer = new int[n][m];
        for (int i = 0; i < n; i++) Arrays.fill(answer[i], -1);
        long ans = 0;
        // i -> m - k + i
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(
            (int[] a, int[] b) -> {
            int col1 = a[0], i1 = a[1];
            int col2 = b[0], i2 = b[1];
            int s1 = x[col1][i1] + x[col1][m - k + i1];
            int s2 = x[col2][i2] + x[col2][m - k + i2];
            return s1 != s2 ? s1 - s2 : col1 - col2;
        });
        for (int i = 0; i < n; i++) {
            pq.add(new int[] { i, 0 });
        }
        int[] until = new int[n];
        for (int s = 0; s < k * (n / 2); s++) {
            int[] p = pq.poll();
            int col = p[0];
            int ind = p[1];
            until[col]++;
            if (ind < k - 1) {
                p[1]++;
                pq.add(p);
            }
        }
        Tickets[] tickets = new Tickets[n];
        for (int i = 0; i < n; i++) {
            tickets[i] = new Tickets(i, x[i], until[i] - 1, m - k + until[i]);
        }
        for (int i = 0; i < k; i++) {
            Arrays.sort(tickets, (Tickets a, Tickets b) -> Math.max(b.numMinus(), b.numPlus()) -
                    Math.max(a.numMinus(), a.numPlus()));
            int balance = 0;
            int numDaysLeft = k - i;
            for (int j = 0; j < n; j++) {
                Tickets t = tickets[j];
                int col = t.color;
                if (t.numMinus() == numDaysLeft) {
                    int index = t.minusTill;
                    t.minusTill--;
                    answer[col][index] = i;
                    balance--;
                } else if (t.numPlus() == numDaysLeft) {
                    int index = t.plusAfter;
                    t.plusAfter++;
                    answer[col][index] = i;
                    balance++;
                } else {
                    if (t.numMinus() == 0) {
                        int index = t.plusAfter;
                        t.plusAfter++;
                        answer[col][index] = i;
                        balance++;
                    } else if (t.numPlus() == 0) {
                        int index = t.minusTill;
                        t.minusTill--;
                        answer[col][index] = i;
                        balance--;
                    } else {
                        if (balance <= 0) {
                            int index = t.plusAfter;
                            t.plusAfter++;
                            answer[col][index] = i;
                            balance++;
                        } else {
                            int index = t.minusTill;
                            t.minusTill--;
                            answer[col][index] = i;
                            balance--;
                        }
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < until[i]; j++) {
                ans -= x[i][j];
            }
            for (int j = until[i] + m - k; j < m; j++) {
                ans += x[i][j];
            }
        }
        grader.allocate_tickets(answer);
        return ans;
    }

    private class Tickets {
        int color;
        int[] val;
        int minusTill;
        int plusAfter;

        Tickets(int col, int[] val, int minusTill, int plusAfter) {
            this.color = col;
            this.val = val;
            this.minusTill = minusTill;
            this.plusAfter = plusAfter;
        }

        int numMinus() {
            return minusTill + 1;
        }

        int numPlus() {
            return val.length - plusAfter;
        }
    }
}

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23
• Subtask 7: 10 / 10